問題#
（翻訳があまりにも簡単すぎたので英語を使用します）
Farmer John は最近オンラインで新しい車を購入しましたが、急いでいたため、車の追加機能を選択する際に「送信」ボタンを二回クリックしてしまい、その結果、車には二つの GPS ナビゲーションシステムが装備されてしまいました！さらに悪いことに、二つのシステムは FJ が取るべきルートについてしばしば対立する決定を下します。
FJ が住んでいる地域の地図は、N の交差点 (2 <= N <= 10,000) と M の方向性道路 (1 <= M <= 50,000) で構成されています。道路 i は交差点 A_i (1 <= A_i <= N) と B_i (1 <= B_i <= N) を接続しています。同じペアの交差点を接続する複数の道路が存在する可能性があり、双方向の道路 (双方向の移動を許可する) は、反対の向きの二つの別々の方向性道路で表されます。FJ の家は交差点 1 にあり、彼の農場は交差点 N にあります。彼の家から農場に到達することは、方向性道路の一連を通って可能です。
両方の GPS ユニットは、上記のように同じ基盤の地図を使用していますが、各道路に沿った移動時間について異なる考え方を持っています。道路 i は、最初の GPS ユニットによると P_i の時間を要し、二番目のユニットによると Q_i の時間を要します (各移動時間は1..100,000の範囲の整数です)。
FJ は自宅から農場に移動したいと考えています。しかし、各 GPS ユニットは、FJ が道路 (例えば、交差点Xから交差点Yに) を通るたびに、その GPS ユニットが農場への最短ルートの一部でないと考える道路について大声で不満を言います (FJがどちらのユニットも好まない道路を通った場合、両方のGPSユニットが不満を言う可能性もあります)。
FJ が適切にルートを選択した場合、彼が受け取る可能性のある不満の最小数を特定する手助けをしてください。FJ が道路を通った際に両方の GPS ユニットが不満を言った場合、これは合計に + 2 としてカウントされます。
入力形式：
- 行 1: 整数 N と M。
行 i は、四つの整数 A_i B_i P_i Q_i で道路 i を説明します。
出力形式：
- 行 1: FJ が自宅から農場に最適にルートを設定した場合に受け取ることができる最小の不満の合計数。
考え方#
それぞれの GPS1 と GPS2 のために二つの逆グラフを構築し、これにより各点から N への最短ルートと各点の最短ルート上の次の辺を求めることができます。
次に FJ のためにグラフを構築し、各辺の初期重みを 2 に設定して警告回数を示します。最短ルートを求める際に、次の辺が特定の GPS と同じであれば、警告回数が 1 減少します。
コード#
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 10000 + 5;
int n, m;
struct mp {
struct ed {
int to, w, nex;
} e[MAXN * 6];
int newp;
int head[MAXN], fa[MAXN], d[MAXN];
bool inq[MAXN];
void lineAdd (int p1, int p2, int w) {
++newp;
e[newp].to = p2;
e[newp].w = w;
e[newp].nex = head[p1];
head[p1] = newp;
}
void spfa (int s) {
memset(inq, 0, sizeof(inq));
memset(d, 0x3f, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = 0;
for (int i = head[u]; i; i = e[i].nex) {
int y = e[i].to;
if (d[u] + (e[i].w) < d[y]) {
d[y] = d[u] + e[i].w;
fa[y] = i;
if (!inq[y]) {
q.push(y);
inq[y] = 1;
}
}
}
}
}
};
mp g1, g2, fj;
void spfa_for_fj(void) {
memset(fj.inq, 0, sizeof(fj.inq));
memset(fj.d, 0x3f, sizeof(fj.d));
queue<int> q;
q.push(1);
fj.d[1] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
fj.inq[u] = 0;
for (int i = fj.head[u]; i; i = fj.e[i].nex) {
int y = fj.e[i].to, w = fj.e[i].w;
if (g1.fa[u] == i) --w;
if (g2.fa[u] == i) --w;
if (fj.d[u] + w < fj.d[y]) {
fj.d[y] = fj.d[u] + w;
if (!fj.inq[y]) {
q.push(y);
fj.inq[y] = 1;
}
}
}
}
}
int main (void) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int p1, p2, w1, w2;
scanf("%d%d%d%d", &p1, &p2, &w1, &w2);
g1.lineAdd(p2, p1, w1);
g2.lineAdd(p2, p1, w2);
fj.lineAdd(p1, p2, 2);
}
g1.spfa(n);
g2.spfa(n);
spfa_for_fj();
printf("%d\n", fj.d[n]);
fclose(stdin);
fclose(stdout);
return 0;
}