ZOJ3946HighwayProject(有条件的最短路)

题目链接&＃xff1a;http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode&＃61;3946

题意&＃xff1a;Marjar帝国的皇帝爱德华想要建造一些双向高速公路&＃xff0c;以便尽可能快地从首都到达其他城市。 因此&＃xff0c;他提出了高速公路项目。Marjar帝国有N个城市&＃xff08;包括首都&＃xff09;&＃xff0c;从0到N  -  1&＃xff08;首都是0&＃xff09;的索引&＃xff0c;并且可以建造M条高速公路。 建设第i高速公路需要Ci美元。 在i-th高速公路上&＃xff0c;Xi到Yi需要Di分钟。

爱德华希望找到一个建筑计划&＃xff0c;从首都到达其他城市所需的总时间最短&＃xff0c;即从首都到城市i所需的最短时间总和&＃xff08;1≤i≤N&＃xff09;。 在所有可行的计划中&＃xff0c;爱德华想要以最低的成本选择计划。 请帮助他完成这项任务。

思路&＃xff1a;这题是在路径最短的境况下选择最少的花费&＃xff0c;所以需要在松弛的时候对花费进行更新操作&＃xff0c;假如说三个点被线连着&＃xff0c;第一个点也连着第三个点&＃xff0c;因为dij对边进行松弛的时候&＃xff0c;总是选择在dis数组里面离源点最近的而且没松弛过的&＃xff0c;所以从最短路径来说&＃xff0c;这个点肯定是最短路径里的点了&＃xff0c;但是如果加了花费这个条件的话&＃xff0c;所以当我们判断如果dis[1-3]&＃61;&＃61;dis[1-2-3]的话&＃xff0c;我们还要判断它们的花费需不需要更新。注意更新的时候花费不要累加&＃xff0c;因为路只要修一遍。

#include
using namespace std;
#define pii pair
#define ll long long
const int N &＃61; 1e5&＃43;7;
vector E[N], Ep[N];
int vis[N], n, m;
ll d[N], p[N];
void init()
{memset(d, 0x3f, sizeof(d));memset(vis, 0, sizeof(vis));for(int i &＃61; 0; i }
void Dijkstra()
{priority_queue Q;Q.push({-d[0], 0});while(!Q.empty()){int now &＃61; Q.top().second;Q.pop();if(vis[now]) continue;vis[now] &＃61; 1;for(int i &＃61; 0; i d[now] &＃43; E[now][i].second){d[v] &＃61; d[now] &＃43; E[now][i].second;p[v] &＃61; Ep[now][i].second;Q.push({-d[v], v});}else if(d[v] &＃61;&＃61; d[now] &＃43; E[now][i].second && p[v] > Ep[now][i].second)p[v] &＃61; Ep[now][i].second;}}
}
int main()
{int t;scanf("%d", &t);while(t--){init();scanf("%d%d", &n, &m);for(int i &＃61; 0; i }