最短路径问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 24687 Accepted Submission(s): 7360 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
Source
Recommend
notonlysuccess
这里采用dijkstra算法。
# include# include # include # define INF 0x3f3f3f3fusing namespace std;int dis[1001][1001], cost[1001][1001], vis[1001], lowcost[1001], lowvalue[1001];int ans1, ans2;void dijkstra(int n, int s, int t){ memset(vis, 0, sizeof(vis)); for(int i=1; i<=n; ++i) { lowcost[i] = dis[s][i]; lowvalue[i] = cost[s][i]; } vis[s] = 1; for(int i=2; i<=n; ++i) { int minid, imin = INF, imin2 = INF; for(int j=1; j<=n; ++j) { if(!vis[j]) { if(lowcost[j] < imin) { imin = lowcost[j]; imin2 = lowvalue[j]; minid = j; } else if(lowcost[j] == imin) imin2 = min(imin2, lowvalue[j]); } } if(imin == INF) break; vis[minid] = 1; for(int j=1; j<=n; ++j) { if(!vis[j]) { if(dis[j][minid]+lowcost[minid] < lowcost[j]) { lowcost[j] = dis[j][minid] + lowcost[minid]; lowvalue[j] = cost[j][minid] + lowvalue[minid]; } else if(dis[j][minid]+lowcost[minid] == lowcost[j]) lowvalue[j] = min(lowvalue[j], cost[j][minid] + lowvalue[minid]); } } } ans1 = lowcost[t]; ans2 = lowvalue[t];}int main(){ int n, m, a, b, d, p, s, t; while(~scanf("%d%d",&n,&m),n+m) { for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) dis[i][j] = dis[j][i] = cost[i][j] = cost[j][i] = INF; while(m--) { scanf("%d%d%d%d",&a,&b,&d,&p); if(dis[a][b] > d) { dis[a][b] = dis[b][a] = d; cost[a][b] = cost[b][a] = p; } else if(dis[a][b] == d) if(cost[a][b] > p) cost[a][b] = cost[b][a] = p; } scanf("%d%d",&s,&t); dijkstra(n, s, t); printf("%d %d\n",ans1, ans2); }}