本文主要是介绍hdu 3790 (单源最短路dijkstra），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
解析：
考察对dijkstra的理解。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int n, m;
int s, t;
int dis[maxn][maxn], cost[maxn][maxn];
bool vis[maxn];void dijkstra()
{memset(vis, false, sizeof(vis));for (int i = 1; i <= n; i++){int mindis = inf, mincost = inf;int mark = -1;for (int j = 1; j <= n; j++){if (!vis[j]){if (dis[s][j] < mindis || (dis[s][j] == mindis && cost[s][j] < mincost)){mindis = dis[s][j];mincost = cost[s][j];mark = j;}}}//vis[mark] = true;for (int j = 1; j <= n; j++){if (!vis[j]){if (dis[s][mark] + dis[mark][j] < dis[s][j] || (dis[s][mark] + dis[mark][j] == dis[s][j] && cost[s][mark] + cost[mark][j] < cost[s][j])){dis[s][j] = dis[s][mark] + dis[mark][j];cost[s][j] = cost[s][mark] + cost[mark][j];}}}}
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d%d", &n, &m)){if (!n && !m)break;for (int i = 0; i < maxn; i++){for (int j = 0; j < maxn; j++){dis[i][j] = (i == j) ? 0 : inf;cost[i][j] = (i == j) ? 0 : inf;}}for (int i = 0; i < m; i++){int u, v, d, c;scanf("%d%d%d%d", &u, &v, &d, &c);if (d < dis[u][v] || (d == dis[u][v] && c < cost[u][v])){dis[u][v] = dis[v][u] = d;cost[u][v] = cost[v][u] = c;}}scanf("%d%d", &s, &t);dijkstra();printf("%d %d\n", dis[s][t], cost[s][t]);}return 0;
}
这篇关于hdu 3790 (单源最短路dijkstra）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
