本文主要是介绍Highway Project （ZOJ - 3946，双权值 spfa），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
ZOJ-3946
二.题目大意：
T 组数据.
第一行两个整数 n，m
之后 m 行数据，每行给出第 i 条路的 {起点，终点，花费时间，花费金钱}
首都为第 0 号城市.
求从首都到其他所有城市所需的 总时间 和 总建路花费.
三.分析：
双权值的单源最短路，更改 if 条件语句里就可以了.
注意：时间可重复加，但花费不可以.
所以直接用 dis2[v] 来记录第 i 条路的花费
之后求和即可.
还有要开 long long int.
详见代码.
四.分析：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;const int M = (int)1e5;
const ll inf = 1ll << 50;struct node
{int u;int v;int c1;int c2;int next;
}Edge[2 * M + 5];int cnt = 0;
bool vis[M + 5];
int head[M + 5];
ll dis1[M + 5];
ll dis2[M + 5];void init(int n)
{cnt = 0;for(int i = 0; i < n; ++i){vis[i] = 0;head[i] = -1;dis1[i] = inf;dis2[i] = inf;}
}void add(int u, int v, int c1, int c2)
{Edge[cnt].u = u;Edge[cnt].v = v;Edge[cnt].c1 = c1;Edge[cnt].c2 = c2;Edge[cnt].next = head[u];head[u] = cnt++;
}struct cmp
{bool operator()(int a, int b){if(dis1[a] == dis1[b])return dis2[a] > dis2[b];return dis1[a] > dis1[b];}
};void spfa(int start)
{vis[start] = 1;dis1[start] = 0;dis2[start] = 0;priority_queue <int, vector <int>, cmp> q;q.push(start);while(!q.empty()){ll u = q.top();q.pop();vis[u] = 0;for(int i = head[u]; ~i; i = Edge[i].next){int v = Edge[i].v;if(dis1[v] >= dis1[u] + Edge[i].c1){if(dis1[v] == dis1[u] + Edge[i].c1)dis2[v] = min(dis2[v], 1ll * Edge[i].c2);elsedis2[v] = 1ll * Edge[i].c2;dis1[v] = dis1[u] + Edge[i].c1;if(!vis[v]){vis[v] = 1;q.push(v);}}}}
}int main()
{int T;scanf("%d", &T);while(T--){int n, m;scanf("%d %d", &n , &m);init(n);for(ll i = 0; i < m; ++i){ll u, v, c1, c2;scanf("%d %d %d %d", &u, &v, &c1, &c2);add(u, v, c1, c2);add(v, u, c1, c2);}spfa(0);ll sum1 = 0;ll sum2 = 0;for(int i = 0; i < n; ++i){sum1 += dis1[i];sum2 += dis2[i];}printf("%lld %lld\n", sum1, sum2);}return 0;
}
这篇关于Highway Project （ZOJ - 3946，双权值 spfa）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
