最短路的简单应用问题。
原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3790
CSUST链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=19760#problem/L
最短路径问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6346 Accepted Submission(s): 1922
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
Source
Recommend
notonlysuccess
解题思路:Dijkstra
求最短路径直接用Dijkstra算法模板即可,由于本题多了个费用问题,所以在松弛dist[y] 时把原来的直接找出最短路径替换变成分情况讨论即可。
1、如果新路径(即沿着代码中 x 出发的边走)路径变短,则任然直接替换,同时更新花费。
2、如果路径长度相等,则选花费小的,只用更新花费即可。
PS: 1、注意是无向图,不要忽略了重边问题。
2、如果你不知道Dijkstra 请先AC这道题 POJ 1847 Tram
http://blog.csdn.net/cfreezhan/article/details/8619040
3、另外推荐 POJ 1062 昂贵的聘礼
http://blog.csdn.net/cfreezhan/article/details/8627216
//8184 KB 187 ms C++ 1534 B 2013-03-01 18:40:56 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1000 + 10; const int INF = 100000000; int w[maxn][maxn]; int value[maxn][maxn]; int dist[maxn],cost[maxn]; bool vis[maxn]; int n,m; int start,end; void Dijkstra() { memset(vis,false,sizeof(vis));//清除所有标点 for(int i=1;i<=n;i++) { dist[i] = w[start][i]; cost[i] = value[start][i]; } dist[start] = 0; //起点自己到自己为0 cost[start] = 0; vis[start] = true; for(int i=1;i<=n;i++) //循环n次 { int x, m = INF; for(int y=1;y<=n;y++) //找出未标记的 dist 的最小的节点x { if(!vis[y] && dist[y] <= m) { m = dist[x=y]; } } vis[x] = true; //标记 x for(int y = 1;y <= n;y++) //松弛操作,更新dist { if(dist[y] > dist[x]+w[x][y]) //如果比dist小可直接更新 { dist[y] = dist[x] + w[x][y]; cost[y] = cost[x] + value[x][y]; } else if(dist[y] == dist[x]+w[x][y]) //如果路径等长, 则选择花费小的 { if(cost[y] > cost[x] + value[x][y]) { cost[y] = cost[x] + value[x][y]; dist[y] = dist[x] + w[x][y];//其实本来就相等 可以省略 } } dist[y] = min(dist[y], dist[x]+w[x][y]); } } printf("%d %d\n",dist[end],cost[end]); } int main() { int a, b, d, p; while(scanf("%d%d", &n, &m)!=EOF) { if(n==0 || m==0) break; for(int i=1;i<=n;i++) //初始化 { dist[i] = INF; cost[i] = INF; for(int j=1;j<=n;j++) { w[i][j] = INF; value[i][j] = INF; } } for(int i=1;i<=m;i++) { scanf("%d%d%d%d", &a, &b, &d, &p); if(d <= w[a][b]) //注意重边问题 { w[a][b] = d; w[b][a] = d; //注意是无向图 value[a][b] = p; value[b][a] = p; } } scanf("%d%d", &start, &end); Dijkstra(); } return 0; }
最近开始学图论了,难得的1A简单题目,看来还是要多学算法,从模板题目开始慢慢做才会有进步呢。