Minimum Transport Cost

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10714    Accepted Submission(s): 2958 点击打开题目链接 Problem Description These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts:  The cost of the transportation on the path between these cities, and a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities. You must write a program to find the route which has the minimum cost.   Input First is N, number of cities. N = 0 indicates the end of input. The data of path cost, city tax, source and destination cities are given in the input, which is of the form: a11 a12 ... a1N a21 a22 ... a2N ............... aN1 aN2 ... aNN b1 b2 ... bN c d e f ... g h where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, ..., and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form:   Output From c to d : Path: c-->c1-->......-->ck-->d Total cost : ...... ...... From e to f : Path: e-->e1-->..........-->ek-->f Total cost : ...... Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case.   Sample Input 5 0 3 22 -1 4 3 0 5 -1 -1 22 5 0 9 20 -1 -1 9 0 4 4 -1 20 4 0 5 17 8 3 1 1 3 3 5 2 4 -1 -1 0   Sample Output From 1 to 3 : Path: 1-->5-->4-->3 Total cost : 21 From 3 to 5 : Path: 3-->4-->5 Total cost : 16 From 2 to 4 : Path: 2-->1-->5-->4 Total cost : 17 题目意思： 第一行输入一个数N，代表城市个数，然后输入N*N的一个矩阵，其数字是城市i到城市j的距离，如果是-1，代表没有路。 然后输入经过每个城市的税收。接着提问m组城市的最短路径。如果最短路径有多条，输出字典序小的那一条路。 比如求城市2->4的最短路径： 存在2->1->5->4 和 2->3->5->4两个都是最短路，要输出2->1->5->4. #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<cstring> #include<string> #include<stack> #include<map> #include<set> #define INF 0x3f3f3f3f #define MAXN 200 using namespace std; int Map[MAXN][MAXN]; int Path[MAXN][MAXN]; int Tax[MAXN]; int N,S,T; void Flody() { for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) { if(Map[i][k]+Map[k][j]+Tax[k] < Map[i][j]) ///与Flody模板的不同点，若经过城市k，则需要加上城市k的税收 { Map[i][j] = Map[i][k]+Map[k][j]+Tax[k]; Path[i][j] = Path[i][k]; ///更新后继节点 } else if(Map[i][k]+Map[k][j]+Tax[k] == Map[i][j]) ///如果最短路径长度相等。要字典序小的。 { if(Path[i][j]>Path[i][k]) { Path[i][j] = Path[i][k]; } } } } void Dispath() ///输出s到t的一条路径 { if(Map[S][T]<INF) { printf("From %d to %d :\n",S,T); int next; printf("Path: "); printf("%d",S); ///先输出起点 next = Path[S][T]; ///从S到T的后继为next while(next != -1) { printf("-->%d",next); next = Path[next][T]; } printf("\nTotal cost : %d\n\n",Map[S][T]); } } int main() { while(~scanf("%d",&N)) { if(N == 0) break; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { scanf("%d",&Map[i][j]); if(Map[i][j]==-1) Map[i][j] = INF; if(i!=j && Map[i][j]<INF) Path[i][j] = j; ///存入后继节点 else Path[i][j] = -1; } } for(int i = 1; i <= N; i++) scanf("%d",&Tax[i]); ///输入某个城市的税 Flody(); while(1) { scanf("%d%d",&S,&T); if(S == -1 && T == -1) break; if(S == T) ///注意起点和终点相等的情况。 { printf("From %d to %d :\n",S,T); printf("Path: %d\n",S); printf("Total cost : %d\n\n",0); } else Dispath(); } } return 0; }