这里起点和终点都是确定的,唯一有点小麻烦(也算不上什么麻烦)就是这里的权值有两个,钱和路长,题目要求选择最短路,对于一样长度的路选择钱最少的路....那么我们每次就对路长松弛,对于路长一样的在对钱松弛....(不懂松弛操作的很抱歉)
// AC 840k 109ms #include<cstdio> #include<queue> using namespace std; #define MAX 1001 #define IFN 1<<30-1 struct node { int to,len,cost,next; }edge[MAX*100*2]; int head[MAX],tol; int n,m,st,end; void init() { int i; for(i=1;i<=n;i++) head[i]=-1; tol=0; int a,b,l,c; for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&l,&c); edge[tol].to=b,edge[tol].len=l,edge[tol].cost=c; edge[tol].next=head[a]; head[a]=tol++; edge[tol].to=a,edge[tol].len=l,edge[tol].cost=c; edge[tol].next=head[b]; head[b]=tol++; } scanf("%d%d",&st,&end); } int d[MAX],cost[MAX]; bool flag[MAX]; int main() { while(scanf("%d%d",&n,&m),n+m) { init(); int i; for(i=1;i<=n;i++) d[i]=IFN,cost[i]=IFN,flag[i]=false; d[st]=0,cost[st]=0; queue<int>q; q.push(st); while(!q.empty()) { int u=q.front();q.pop();flag[u]=false; for(int j=head[u];j!=-1;j=edge[j].next) { int v=edge[j].to,l=edge[j].len,c=edge[j].cost; if(d[v]>d[u]+l || (d[v]==d[u]+l) && cost[v]>cost[u]+c) { d[v]=d[u]+l;cost[v]=cost[u]+c; if(!flag[v]) q.push(v),flag[v]=true; } } } printf("%d %d\n",d[end],cost[end]); } return 0; }