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)
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; 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); } } /* 5 7 1 2 5 5 2 3 4 5 1 3 4 6 3 4 2 6 3 5 4 7 4 5 2 6 1 3 4 4 1 5 8 11 5 7 1 2 5 5 2 3 4 5 1 3 4 6 3 4 2 2 3 5 4 7 4 5 2 4 1 3 4 4 1 5 8 10 */ #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;
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);
}
}
/*
5 7
1 2 5 5
2 3 4 5
1 3 4 6
3 4 2 6
3 5 4 7
4 5 2 6
1 3 4 4
1 5
8 11
5 7
1 2 5 5
2 3 4 5
1 3 4 6
3 4 2 2
3 5 4 7
4 5 2 4
1 3 4 4
1 5
8 10
*/
