有兩個權值,距離相等的時候判斷一下花費
最短路徑問題
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11075 Accepted Submission(s): 3348
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
Output
輸出 一行有兩個數， 最短距離及其花費。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
Source
浙大計算機研究生復試上機考試-2010年
#include
#include
#include
#include
using namespace std;
const int maxn=1100;
const int INF=0x3f3f3f3f;
int c[maxn][maxn],w[maxn][maxn];
int n,m;
int origional,vis[maxn],dist[maxn],cost[maxn];
void dijkstra()
{
memset(vis,0,sizeof(vis));
memset(dist,63,sizeof(dist));
memset(cost,63,sizeof(cost));
cost[origional]=dist[origional]=0;
for(int l=0;ldist[i])
{
mark=i;
mindist=dist[i];
}
}
vis[mark]=1;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(dist[i]>dist[mark]+w[mark][i])
{
dist[i]=dist[mark]+w[mark][i];
cost[i]=cost[mark]+c[mark][i];
}
else if(dist[i]==dist[mark]+w[mark][i]&&cost[i]>cost[mark]+c[mark][i])
{
cost[i]=cost[mark]+c[mark][i];
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
memset(c,63,sizeof(c));
memset(w,63,sizeof(w));
int a,b,d,p;
for(int i=0;i
