本文主要是介绍hdu 3790 最短路径问题(两个限制条件的最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3790
有两个条件：距离和花费。首先要求距离最短，距离相等的条件下花费最小。
dijkstra，只是在判断条件时多考虑了花费。
注意重边。
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <stack>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 1010;
int Map[maxn][maxn],cost[maxn][maxn];
int n,m;
int dis1[maxn],dis2[maxn];void init()
{for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j){Map[i][j] = 0;cost[i][j] = 0;}else{Map[i][j] = INF;cost[i][j] = INF;}}}
}void dijkstra(int s, int t)
{int vis[maxn];memset(dis1,INF,sizeof(dis1));memset(dis2,INF,sizeof(dis2));memset(vis,0,sizeof(vis));for(int i = 1; i <= n; i++){dis1[i] = Map[s][i];dis2[i] = cost[s][i];}vis[s] = 1;for(int i = 1; i <= n; i++){int M1= INF, M2 = INF, pos;for(int j = 1; j <= n; j++){if(vis[j]) continue;if(dis1[j] < M1 || (dis1[j] == M1 && dis2[j] < M2)){M1 = dis1[j];M2 = dis2[j];pos = j;}}vis[pos] = 1;for(int j = 1; j <= n; j++){if(vis[j]) continue;int tmp1 = dis1[pos] + Map[pos][j];int tmp2 = dis2[pos] + cost[pos][j];if(tmp1 < dis1[j] || (tmp1 == dis1[j] && tmp2 < dis2[j])){dis1[j] = tmp1;dis2[j] = tmp2;}}}
}int main()
{while(~scanf("%d %d",&n,&m)){if(n == 0 || m == 0) break;init();int a,b,d,p;while(m--){scanf("%d %d %d %d",&a,&b,&d,&p);if(Map[a][b] == INF && cost[a][b] == INF){Map[a][b] = Map[b][a] = d;cost[a][b] = cost[b][a] = p;}else if(d < Map[a][b] || (Map[a][b] == d && cost[a][b] > p)){Map[a][b] = Map[b][a]= d;cost[a][b] = cost[b][a] = p;}}scanf("%d %d",&a,&b);dijkstra(a,b);printf("%d %d\n",dis1[b],dis2[b]);}return 0;
}
这篇关于hdu 3790 最短路径问题(两个限制条件的最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
