准备考研，荒废了好多东西，希望做了正确的决定
/********************************************************* *author：chen xin *email：cx2pirate@gmail.com *date：2014.09.09 * *******************************************************/#include#include #define MAXINT 0x7fffffff#define MAXN 1005typedef struct{ int dis,cost;}RECORD;RECORD record[MAXN];RECORD map[MAXN][MAXN];int vis[MAXN];// O(v + e)void init(int n);RECORD dijkstra(int n,int m,int f,int t);int main(void){ int n,m,f,t; int u,v,dis,cost; while(scanf("%d%d",&n,&m) && n && m){ init(n); for(int i = 0;i < m;i++){ scanf("%d%d%d%d",&u,&v,&dis,&cost); if(map[u][v].dis > dis || map[u][v].dis == dis && map[u][v].cost > cost){ map[u][v].dis = map[v][u].dis = dis; map[u][v].cost = map[v][u].cost = cost; } } scanf("%d%d",&f,&t); RECORD res = dijkstra(n,m,f,t); printf("%d %d\n",res.dis,res.cost); } return 0;}void init(int n){ for(int i = 1;i <= n;i++){ vis[i] = 0; record[i].dis = record[i].cost = MAXINT; for(int j = 1;j <= n;j++){ map[i][j].dis = map[i][j].cost = MAXINT; } }}int relaxable(RECORD u,RECORD v,RECORD edge){ if((u.dis + edge.dis) < v.dis){ return 1; } if(u.dis + edge.dis == v.dis && u.cost + edge.cost < v.cost){ return 1; } return 0;}RECORD dijkstra(int n,int m,int f,int t){ record[f].dis = record[f].cost = 0; for(int i = 1;i <= n;i++){ int min,min_dis = MAXINT,min_cost = MAXINT; for(int j = 1;j <= n;j++){ if(!vis[j] && (record[j].dis < min_dis || record[j].dis == min_dis && record[j].cost < min_cost)) { min = j; min_dis = record[j].dis; min_cost = record[j].cost; } } vis[min] = 1; for(int k = 1;k <= n;k++){ if(!vis[k] && map[min][k].dis < MAXINT && relaxable(record[min],record[k],map[min][k])) { record[k].dis = record[min].dis + map[min][k].dis; record[k].cost = record[min].cost + map[min][k].cost; } } } return record[t];}//11626983 2014-09-09 23:02:13 Accepted 3790 312MS 8144K 2232 B G++ 超级旅行者