http://acm.hdu.edu.cn/showproblem.php?pid=3790
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1001 5 using namespace std; 6 const int inf=1<<28; 7 8 int g[maxn][maxn]; 9 int cost[maxn][maxn]; 10 int n,m,a,b,d,p,s,e; 11 bool vis[maxn]; 12 int dis[maxn],c[maxn]; 13 14 void inti() 15 { 16 for(int i=1; i<=n; i++) 17 { 18 for(int j=1; j<=n; j++) 19 { 20 if(i==j) 21 { 22 g[i][j]=0; 23 cost[i][j]=0; 24 } 25 else 26 { 27 g[i][j]=inf; 28 cost[i][j]=inf; 29 } 30 } 31 } 32 } 33 34 void dijkstra(int str) 35 { 36 memset(vis,false,sizeof(vis)); 37 for(int i=1; i<=n; i++) 38 { 39 dis[i]=g[str][i]; 40 c[i]=cost[str][i]; 41 } 42 dis[str]=0; 43 c[str]=0; vis[str]=true; 44 for(int i=1; i<n; i++) 45 { 46 int m=inf,x; 47 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y]; 48 vis[x]=true; 49 for(int y=1; y<=n; y++) 50 { 51 if(!vis[y]&&g[x][y]!=inf) 52 { 53 if(dis[y]>dis[x]+g[x][y]) 54 { 55 dis[y]=dis[x]+g[x][y]; 56 c[y]=c[x]+cost[x][y]; 57 } 58 else if(dis[y]==dis[x]+g[x][y]) 59 { 60 if(c[y]>c[x]+cost[x][y]) 61 c[y]=c[x]+cost[x][y]; 62 } 63 } 64 } 65 } 66 } 67 int main() 68 { 69 while(scanf("%d%d",&n,&m)!=EOF) 70 { 71 if(n==0&&m==0) break; 72 inti(); 73 for(int i=0; i<m; i++) 74 { 75 scanf("%d%d%d%d",&a,&b,&d,&p); 76 if(d<g[a][b]) 77 { 78 g[a][b]=g[b][a]=d; 79 cost[a][b]=cost[b][a]=p; 80 } 81 82 } 83 scanf("%d%d",&s,&e); 84 dijkstra(s); 85 printf("%d %d ",dis[e],c[e]); 86 } 87 return 0; 88 }