例5.6 最短路径问题
#include<stdio.h> #include<vector> using namespace std; bool mark[1001]; int dis[1001]; int cost[1001]; struct Edge { int d; int p; int next; }; vector <Edge> edge[100000]; int main() { int n,m,s,t; while(scanf("%d%d",&n,&m)!=EOF) { if(m==0&&n==0) break; for(int i=1;i<=n;i++) edge[i].clear(); for(int i=0;i<m;i++) { Edge tmp; int a,b,c,e; scanf("%d%d%d%d",&a,&b,&c,&e); tmp.d=c; tmp.p=e; tmp.next=b; edge[a].push_back(tmp); tmp.next=a; edge[b].push_back(tmp); } scanf("%d%d",&s,&t); for(int i=1;i<=n;i++) { mark[i]=false; dis[i]=-1; cost[i]=0; } dis[s]=0; mark[s]=true; int newp=s; for(int i=1;i<n;i++) { for(int j=0;j<edge[newp].size();j++) { int t=edge[newp][j].next; if(mark[t]==true) continue; int dd=edge[newp][j].d; int pp=edge[newp][j].p; if(dis[t]==-1||dis[t]>dis[newp]+dd||dis[t]==dis[newp]+dd&&cost[t]>pp+cost[newp]) { dis[t]=dis[newp]+dd; cost[t]=pp+cost[newp]; } } int min=123123123; for(int j=1;j<=n;j++) { if(mark[j]==true) continue; if(dis[j]==-1) continue; if(dis[j]<min) { min=dis[j]; newp=j; } } mark[newp]=true; } printf("%d %d\n",dis[t],cost[t]); } return 0; }