题目描述：求图上一个点到另一个点的最短距离 以及最小花费。
解题报告：这题用迪杰斯特拉算法是没有疑问，但是重点就是花费最小的问题，这个只要再开一个数组单独存放花费就可以了，其他的跟最短路径是一样的，但是这题我交了n次，就是 因为在输入的处理上，感觉这题也有点坑，题目上并没有说两个点之间可能有多条路径，但事实却是存在两个点之间有多条路径的可能，弄得我WA到死，后来看了别人的报告才发现，问题就出在我在取重复的路径的最小值的问题上，取最小值的时候千万不能简单的将路径跟花费分开求最小值，还要考虑到路径跟花费是有关系的，要更新必须经过特殊的处理，即先判断两点之间的长度是否大于后来输入的长度，如果是，则将这两点之间的长度和花费无条件更换，如果后来输入的长度跟原来的长度相等，那么在两条路径之间取花费较小的就可以了。代码附上：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 const int MAX = 1000+5,inf = 1061109568; 5 int map[MAX][MAX][2],visit[MAX],T[MAX],cost[MAX],n,m; 6 7 int main() { 8 int a,b,d,p,s,e; 9 while(scanf("%d%d",&n,&m),n+m) { 10 memset(map,0x3f,sizeof(map)); 11 memset(cost,0x3f,sizeof(cost)); 12 memset(T,0x3f,sizeof(T)); 13 for(int i = 1;i<=m;++i) { 14 scanf("%d%d%d%d",&a,&b,&d,&p); 15 if(d<map[a][b][0]) { //对于输入的处理很重要 16 map[a][b][0] = map[b][a][0] = d; 17 map[a][b][1] = map[b][a][1] = p; 18 } 19 else if(d==map[a][b][0]) 20 map[a][b][1] = map[b][a][1] = std::min(map[a][b][1],p); 21 } 22 scanf("%d%d",&s,&e); 23 T[s] = cost[s] = 0; //将起点的花费和路径长度都赋0 24 T[0] = inf-1; //为便于更新s的值，将T[0]赋无穷大 25 memset(visit,0,sizeof(visit)); 26 while(1) { 27 for(int i = 1;i<=n;++i) 28 if(!visit[i]&&(T[s]+map[s][i][0])<=T[i]) { 29 if(T[s]+map[s][i][0]<T[i]) { //这一步的处理很重要，要将等于和小于的情况分开处理 30 T[i] = T[s] + map[s][i][0]; 31 cost[i] = cost[s] + map[s][i][1]; 32 } 33 else if(T[s]+map[s][i][0]==T[i]) 34 cost[i] = std::min(cost[i],cost[s] + map[s][i][1]); 35 } 36 visit[s] = 1; 37 s = 0; //将s做初始化处理 38 bool flag = 1; 39 for(int i = 1;i<=n;++i) 40 if(!visit[i]&&T[i]<T[s]) { 41 flag = 0; 42 s = i; 43 } 44 if(flag) //设置退出条件 45 break; 46 } 47 printf("%d %d\n",T[e],cost[e]); 48 } 49 return 0; 50 }