題目描述
最近，Elaxia和w**的關(guān)系特別好，他們很想整天在一起，但是大學(xué)的學(xué)習(xí)太緊張了，他們 必須合理地安排兩個(gè)人在一起的時(shí)間。Elaxia和w**每天都要奔波于宿舍和實(shí)驗(yàn)室之間，他們 希望在節(jié)約時(shí)間的前提下，一起走的時(shí)間盡可能的長(zhǎng)。 現(xiàn)在已知的是Elaxia和w**所在的宿舍和實(shí)驗(yàn)室的編號(hào)以及學(xué)校的地圖：地圖上有N個(gè)路 口，M條路，經(jīng)過(guò)每條路都需要一定的時(shí)間。 具體地說(shuō)，就是要求無(wú)向圖中，兩對(duì)點(diǎn)間最短路的最長(zhǎng)公共路徑。
輸入輸出格式
輸入格式：
第一行：兩個(gè)整數(shù)N和M（含義如題目描述）。 第二行：四個(gè)整數(shù)x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分別表示Elaxia的宿舍和實(shí)驗(yàn)室及w**的宿舍和實(shí)驗(yàn)室的標(biāo)號(hào)（兩對(duì)點(diǎn)分別 x1,y1和x2,y2）。 接下來(lái)M行：每行三個(gè)整數(shù)，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之間有一條路，經(jīng)過(guò)這條路所需要的時(shí)間為l。
輸出格式：
一行，一個(gè)整數(shù)，表示每天兩人在一起的時(shí)間（即最長(zhǎng)公共路徑的長(zhǎng)度）
說(shuō)明
對(duì)于30%的數(shù)據(jù)，N ≤ 100； 對(duì)于60%的數(shù)據(jù)，N ≤ 1000； 對(duì)于100%的數(shù)據(jù)，N ≤ 1500，輸入數(shù)據(jù)保證沒有重邊和自環(huán)。
Analysis
題意已經(jīng)很粗暴了 首先要找到哪些邊在最短路上，可以想到如果dis_to_st[i] + dis_to_ed[j] + w[i, j] = 最短路的話，這條邊處在最短路上 為了求出這些距離我們把給出的四個(gè)點(diǎn)我們分別跑spfa一共是四次，再把共有的邊連成一張新的圖拓?fù)渑判蜃鲞f推，len[u]=max(len[v]+w,len[u]) 就這樣，寫寫停停中途打了兩個(gè)小時(shí)fgo一個(gè)下午吧
Code
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <string>#include <vector>#include <deque>#include <list>#include <set>#include <map>#include <stack>#include <queue>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#define debug puts("-----")#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)#define fill(x, t) memset(x, t, sizeof(x))#define min(x, y) x<y?x:y#define max(x, y) x>y?x:y#define PI (acos(-1.0))#define EPS (1e-8)#define INF (1<<30)#define ll long long#define db double#define ld long double#define N 1501#define E N * N / 2 + 1#define MOD 100000007#define L 255using namespace std;struct edge{int x, y, w, next;}e[E], g[E];int inQueue[N], mark[E], dis1[N], dis2[N], ind[N], lsE[N], lsG[N], dp[N];inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v;}inline int addEdgeE(int &cnt, const int &x, const int &y, const int &w){ e[++ cnt] = (edge){x, y, w, lsE[x]}; lsE[x] = cnt; return 0;}inline int addEdgeG(int &cnt, const int &x, const int &y, const int &w){ g[++ cnt] = (edge){x, y, w, lsG[x]}; lsG[x] = cnt; ind[y] += 1; return 0;}inline int spfa1(const int &st, const int &ed){ fill(inQueue, 0); inQueue[st] = 1; fill(dis1, 63); dis1[st] = 0; queue<int>q; q.push(st); while (!q.empty()){ int now = q.front(); q.pop(); for (int i = lsE[now]; i; i = e[i].next){ if (dis1[now] + e[i].w < dis1[e[i].y]){ dis1[e[i].y] = dis1[now] + e[i].w; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; q.push(e[i].y); } } } inQueue[now] = 0; } return dis1[ed];}inline int spfa2(const int &st, const int &ed){ fill(inQueue, 0); inQueue[st] = 1; fill(dis2, 63); dis2[st] = 0; queue<int>q; q.push(st); while (!q.empty()){ int now = q.front(); q.pop(); for (int i = lsE[now]; i; i = e[i].next){ if (dis2[now] + e[i].w < dis2[e[i].y]){ dis2[e[i].y] = dis2[now] + e[i].w; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; q.push(e[i].y); } } } inQueue[now] = 0; } return dis2[ed];}int main(void){ int n = read(), m = read(); int st1 = read(), ed1 = read(), st2 = read(), ed2 = read(); int edgeCntE = 0, edgeCntG = 0; rep(i, 1, m){ int x = read(), y = read(), w = read(); addEdgeE(edgeCntE, x, y, w); addEdgeE(edgeCntE, y, x, w); } int stpath1 = spfa1(st1, ed1) & spfa2(ed1, st1); //
