Elaxia的路線 SDOI2009 最短路

2019-11-14 09:51:49

字體：大中小

來源：轉載

供稿：網友

題目描述

最近，Elaxia和w**的關系特別好，他們很想整天在一起，但是大學的學習太緊張了，他們必須合理地安排兩個人在一起的時間。Elaxia和w**每天都要奔波于宿舍和實驗室之間，他們希望在節約時間的前提下，一起走的時間盡可能的長。現在已知的是Elaxia和w**所在的宿舍和實驗室的編號以及學校的地圖：地圖上有N個路口，M條路，經過每條路都需要一定的時間。具體地說，就是要求無向圖中，兩對點間最短路的最長公共路徑。

輸入輸出格式

輸入格式：

第一行：兩個整數N和M（含義如題目描述）。第二行：四個整數x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分別表示Elaxia的宿舍和實驗室及w**的宿舍和實驗室的標號（兩對點分別 x1,y1和x2,y2）。接下來M行：每行三個整數，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之間有一條路，經過這條路所需要的時間為l。

輸出格式：

一行，一個整數，表示每天兩人在一起的時間（即最長公共路徑的長度）

說明

對于30%的數據，N ≤ 100；對于60%的數據，N ≤ 1000；對于100%的數據，N ≤ 1500，輸入數據保證沒有重邊和自環。

Analysis

題意已經很粗暴了首先要找到哪些邊在最短路上，可以想到如果dis_to_st[i] + dis_to_ed[j] + w[i, j] = 最短路的話，這條邊處在最短路上為了求出這些距離我們把給出的四個點我們分別跑spfa一共是四次，再把共有的邊連成一張新的圖拓撲排序做遞推，len[u]=max(len[v]+w,len[u]) $len[u]=/max(len[v] + w, len[u])$ 就這樣，寫寫停停中途打了兩個小時fgo一個下午吧

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); //