HDU 3790 最短路

本文主要是介绍HDU 3790 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*这个题目要注意的是当路径相同时要取费用最少的哪一条其它的只要按照最短路的常规用法即可
*/
#include<iostream>
using namespace std;
const int maxn = 1000000;
int n, m, d[1002][1002], p[1002][1002], dis[1002], pis[1002];
bool vis[1002];void Dijk(int st, int ed)
{for(int i = 1; i <= n; i++)//从1-n{dis[i] = d[st][i];pis[i] = p[st][i];}vis[st] = true;for(int k = 1; k < n; k++){int Min = maxn, mj = -1;for(int i = 1; i <= n; i++)if(!vis[i] && dis[i]<Min) Min = dis[i], mj = i;vis[mj] = true;for(int i = 1; i <= n; i++){if(!vis[i] && dis[i]>dis[mj]+d[mj][i])//必须保证mj-i要有通路{dis[i] = dis[mj]+d[mj][i];pis[i] = pis[mj]+p[mj][i];}if(!vis[i] && dis[i]==dis[mj]+d[mj][i] && pis[i]>pis[mj]+p[mj][i])pis[i] = pis[mj]+p[mj][i];}}cout << dis[ed] << " " << pis[ed] << endl;
}int main()
{while(cin >> n >> m && n||m){int st, ed;for(int i = 1; i <= n; i++){vis[i] = false;for(int j = 1; j <= n; j++)if(i != j) d[i][j] = d[j][i] = p[i][j] = p[j][i] = maxn;else d[i][j] = p[i][j] = 0;}while(m--){int a, b, c, e;cin >> a >> b >> c >> e;if(d[a][b] > c){d[a][b] = d[b][a] = c;p[a][b] = p[b][a] = e;}if(d[a][b] == c)if(p[a][b] > c)p[a][b] = p[b][a] = e;}cin >> st >> ed;Dijk(st,ed);}return 0;
}

这篇关于HDU 3790 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---