Problem Description
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
(1<n<=1000, 0<m<100000, s != t)
Output
输出 一行有两个数, 最短距离及其花费。
Sample Input
3 2 1 2 5 6 2 3 4 5 1 3 0 0
Sample Output
9 11优先队列:
#include<stdio.h> #include<iostream> #include<queue> using namespace std; typedef struct n1 { int x,dist,mony; friend bool operator<(n1 a,n1 b) { if(b.dist>a.dist) return b.dist<a.dist; else if(b.dist==a.dist&&b.mony>=a.mony) return b.mony<a.mony; } }node; node map[1005][1005],N[1005]; int s,t,min_dist,min_mony; int vist[1005][1005]; void set(int n,int m) { int i,j,n1,n2,d,p; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map[i][j].dist=0;vist[i][j]=0; } } while(m--) { scanf("%d%d%d%d",&n1,&n2,&d,&p); if(map[n1][n2].dist==d) { if(map[n1][n2].mony>p) map[n1][n2].mony=map[n2][n1].mony=p; } else if(map[n1][n2].dist==0||map[n1][n2].dist>d) { map[n1][n2].dist=map[n2][n1].dist=d; map[n1][n2].mony=map[n2][n1].mony=p; } } scanf("%d%d",&s,&t); } void BFS(int n) { priority_queue<node> Q; node q,p; int i; q.mony=0; q.dist=0;q.x=t; Q.push(q); while(!Q.empty()) { q=Q.top(); Q.pop(); if(q.x==s) { min_dist=q.dist;min_mony=q.mony; break; } for(i=1;i<=n;i++) if(map[q.x][i].dist&&!vist[q.x][i]) { vist[q.x][i]=vist[i][q.x]=1;//这样就不会走重复的路 p.dist=map[q.x][i].dist+q.dist; p.mony=map[q.x][i].mony+q.mony; p.x=i;//printf("%d %d %d\n",p.x,p.dist,p.mony); Q.push(p); } } } int main() { int n,m; while(scanf("%d%d",&n,&m)>0&&(n||m)) { set(n,m); BFS(n); printf("%d %d\n",min_dist,min_mony); } }
dijkstar:
#include<stdio.h> #define INF 99999999 struct nn { int d,p; }map[1005][1005],node[1005]; int N,s[1005]; void init() { for(int i=0;i<=N;i++) { s[i]=0; node[i].d=INF; node[i].p=INF; for(int j=0;j<=N;j++) map[i][j].d=INF,map[i][j].p=INF; } } void dijkstar(int m,int end) { int tm=m; nn min; s[m]=1; node[m].d=0; node[m].p=0; if(m==end)return ; for(int k=2;k<=N;k++) { min.d=INF; min.p=INF; for(int i=1;i<=N;i++) if(s[i]==0) { if(node[i].d>map[tm][i].d+node[tm].d) { node[i].d=map[tm][i].d+node[tm].d; node[i].p=node[tm].p+map[tm][i].p; } else if(node[i].d==map[tm][i].d+node[tm].d) if(node[i].p>map[tm][i].p+node[tm].p) node[i].p=map[tm][i].p+node[tm].p; if(node[i].d<min.d) { min=node[i]; m=i; } else if(node[i].d==min.d&&node[i].p<min.p) min.p=node[i].p,m=i; } s[m]=1;tm=m; if(s[end]) return ; } } int main() { int m,a,b,d,p,sta,end; while(scanf("%d%d",&N,&m)>0&&(N!=0||m!=0)) { init(); while(m--) { scanf("%d%d%d%d",&a,&b,&d,&p); if(map[a][b].d>d) { map[a][b].d=map[b][a].d=d; map[a][b].p=map[b][a].p=p; } else if(map[a][b].d==d&&map[a][b].p>p) map[a][b].p=map[b][a].p=p; } scanf("%d%d",&sta,&end); dijkstar(sta,end); printf("%d %d\n",node[end].d,node[end].p); } }