最短路徑問題
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 17968 Accepted Submission(s): 5385
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
模板題變了點點形，就是每個邊權值包含兩個信息，長度與花費。
切記不能將花費與距離分開考慮，按照題目意思先考慮距離值，若相等再考慮花費值。
具體代碼如下：
#include
#include
#define max 1010
#define INF 0x3f3f3f
int map[max][max],map_cost[max][max],n;
void dijkstra(int start,int end)
{
int dis[max],visit[max],cost[max];
int i,j,min,next=start;
for(i=1;i<=n;++i)
{
dis[i]=map[start][i];
cost[i]=map_cost[start][i];
visit[i]=0;
}
visit[start]=1;
for(i=1;i<=n;++i)
{
min=INF;
for(j=1;j<=n;++j)
{
if(!visit[j]&&min>dis[j])
{
next=j;
min=dis[j];
}
}
visit[next]=1;
for(j=1;j<=n;++j)
{
if(!visit[j])
{
if(dis[j]>dis[next]+map[next][j])
{
dis[j]=dis[next]+map[next][j];
cost[j]=cost[next]+map_cost[next][j];
}
else if(dis[j]==dis[next]+map[next][j]&&cost[j]>cost[next]+map_cost[next][j])
cost[j]=cost[next]+map_cost[next][j];
}
}
}
printf(%d %d
,dis[end],cost[end]);
}
int main()
{
int m,i,j,a,b,d,p,start,end;
while(scanf(%d%d,&n,&m)&&n||m)
{
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(i==j)
map[i][j]=map_cost[i][j]=0;
else
map[i][j]=map_cost[i][j]=INF;
}
}
while(m--)
{
scanf(%d%d%d%d,&a,&b,&d,&p);
if(map[a][b]>d)
{
map[a][b]=map[b][a]=d;
map_cost[a][b]=map_cost[b][a]=p;
}
if(map[a][b]==d&&map_cost[a][b]>p)
map_cost[a][b]=map_cost[b][a]=p;
}
scanf(%d%d,&start,&end);
dijkstra(start,end);
}
return 0;
}
