1.题意简述
有一张有向图，两种 \(GPS\) 的 联通情况相同，但连边的路径长度不同。现在在 \(1\) 到 \(n\) 中找一条路，使其与两个 \(GPS\) 的最短路差异最小。
2.样例解释
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
1
先根据样例画出图形：
然后我们可以算出每个点到 \(n\) 号节点的最短路，即：
所以不难发现，第一个导航最希望的道路是 \(1->3->4\)，第二个导航最希望的道路是 \(1->2->4->5\)。
当然，如果 \(FJ\) 选择其他道路，那么导航会自动切换从当前点到终点的最短道路。也就是说，当 \(FJ\) 从点 \(i\) 出发，走的边不是\(GPS\) 认为的从点 \(i\) 出发去终点所要走的边时（即不在点 \(i\) 到终点的最短路上）就会发出警告。
回归样例，当他走的是 \(1->2->4->5\) 这条道路时，第一个导航会在 \(1->2\) 这条边警告，然后到了 \(2\) 号点后再计算的最短路就和剩下路径一样了，所以答案就是 \(1\)。
3.思路
这道题很明显就是一道最短路。但是我们再做题前要先明白最短路的运行性质：
当第 \(i\) 个点和第 \(j\) 个点通过第 \(k\) 条边直接联通，且正在用第 \(i\) 条边当前的最短路更新 \(j\) 的最短路时，有以下公式：（令 \(L(i, j)\) 表示 \(i\) 到 \(j\) 路径的长度）
当 \(i\) 到终点的距离被更新时，\(dis_j > dis_i + L(i, j)\)，当点 \(j\) 的距离被更新时，\(dis_j < dis_i + L(i, j)\)
特殊的，当两点到终点距离都被更新时，如果更新后 \(i\) 仍在 \(j\) 到 \(n\) 的最短路上，则仍保持 \(dis_j = dis_i + L(i, j)\)，否则 \(dis_j > dis_i + L(i, j)\)
但是，知道了这么多，题目要怎么写呢？如何判断导航是否要警告呢？我们不难发现，当导航警告时，说明 \(i\) 不在 \(j\) 的最短路上了，也就是 \(dis_j > dis_i + L(i, j)\)。而这个式子中的每个量我们都是能算出来的。
那么现在问题又来了：我应该怎么统计最小警告总次数呢？也很简单，只需再开一张图，将每条边可能鸣笛总次数存为其边权，再跑一遍最短路即可。
然后我们就可以按照以下方式做题：
-
1.跑第一遍最短路，将第一个导航中每个点到终点的距离存在数组 \(dis1[]\) 中；
-
2.跑第二遍最短路，将第二个导航中每个点到终点的距离存在数组 \(dis2[]\) 中；
-
3.枚举每条边，分别判断两个导航是否需要警告，将每条边警告总次数存为其边权；
-
4.跑第三遍最短路，输出最终警告次数。
4.注意事项
-
1.在跑最短路时，因为是从 \(n\) 跑到 \(1\)，所以存边时要反着存，在统计答案时，因为图是反着存的，所以也是从终点出发，最后输出起点的警告次数。
-
2.每次最短路时，都要先把存图用的数组清空，避免爆炸。
-
3.因为这道题要跑三遍最短路，这里建议写一个函数，用指针分别指向三个存最短路的数组，让代码看起来更清爽。。。
5.代码：
#include <bits/stdc++.h>
// #define int long long
using namespace std;
#define N 200010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(),cin.tie(),cout.tie()
typedef pair <int, int> PII;
struct no {
int a, b, w1, w2;
}ed[N];
int n, m;
int idx = 0, h[N], w[N], e[N], ne[N];
int dis1[N], dis2[N], dis3[N], st[N];
void add (int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra (int ss, int *dis) { //*dis是指针，分别指向三个存最短路的数组
For (i, 1, n) dis[i] = 0x3f3f3f3f; //指针数组不能用memset
memset (st, 0, sizeof st);
dis[ss] = 0;
priority_queue <PII, vector <PII>, greater <PII> > p;
p.push ({0, ss});
while (!p.empty ()) {
auto t = p.top ();
p.pop ();
int ver = t.second, dit = t.first;
if (st[ver]) {
continue;
}
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dit + w[i]) {
dis[j] = dit + w[i];
p.push ({dis[j], j});
}
}
}
} //标准模板dijkstra
signed main () {
IOS;
cin >> n >> m;
For (i, 1, m) {
int x, y, w1, w2;
cin >> x >> y >> w1 >> w2;
ed[i] = {y, x, w1, w2}; //从y连到x,注意存反边
}
memset (h, -1, sizeof h);
idx = 0; //第一次清空
For (i, 1, m) add (ed[i].a, ed[i].b, ed[i].w1); //根据第一个导航建边
dijkstra (n, dis1);
memset (h, -1, sizeof h);
idx = 0; //第二次清空
For (i, 1, m) add (ed[i].a, ed[i].b, ed[i].w2); //根据第二个导航建边
dijkstra (n, dis2);
// For (i, 1, n) {cout << dis1[i] << ' ';} cout << endl;
// For (i, 1, n) {cout << dis2[i] << ' ';} cout << endl;
memset (h, -1, sizeof h);
idx = 0; //第三次清空
For (i, 1, m) {
int cnt = 0; //存储第i条边的警告次数
if (dis1[ed[i].b] != dis1[ed[i].a] + ed[i].w1) cnt ++; //第一个导航
if (dis2[ed[i].b] != dis2[ed[i].a] + ed[i].w2) cnt ++; //第二个导航
add (ed[i].a, ed[i].b, cnt); //建边，边权为其警告次数
}
dijkstra (n, dis3); //还是倒着跑
cout << dis3[1] << endl; //输出起点的警告次数
return 0;
} //完结撒花！！！！！！