Codevs 1021 瑪麗卡

題目地址：http://codevs.cn/problem/1021/

題目描述 Description

麥克找了個(gè)新女朋友，瑪麗卡對(duì)他非常惱火并伺機(jī)報(bào)復(fù)。
因?yàn)樗退麄儾蛔≡谕粋€(gè)城市，因此她開始準(zhǔn)備她的長(zhǎng)途旅行。
在這個(gè)國(guó)家中每?jī)蓚€(gè)城市之間最多只有一條路相通，并且我們知道從一個(gè)城市到另一個(gè)城市路上所需花費(fèi)的時(shí)間。
麥克在車中無意中聽到有一條路正在維修，并且那兒正堵車，但沒聽清楚到底是哪一條路。無論哪一條路正在維修，從瑪麗卡所在的城市都能到達(dá)麥克所在的城市。
瑪麗卡將只從不堵車的路上通過，并且她將按最短路線行車。麥克希望知道在最糟糕的情況下瑪麗卡到達(dá)他所在的城市需要多長(zhǎng)時(shí)間，這樣他就能保證他的女朋友離開該城市足夠遠(yuǎn)編寫程序，幫助麥克找出瑪麗卡按最短路線通過不堵車道路到達(dá)他所在城市所需的最長(zhǎng)時(shí)間(用分鐘表示)。

輸入描述 Input Description

第一行有兩個(gè)用空格隔開的數(shù)N和M，分別表示城市的數(shù)量以及城市間道路的數(shù)量。1≤N≤1000，1≤M≤N?(N?1)/2。城市用數(shù)字1 至 N標(biāo)識(shí)，麥克在城市 1 中，瑪麗卡在城市 N 中。
接下來的M行中每行包含三個(gè)用空格隔開的數(shù)A，B和V。其中1≤A，B≤N，1≤V≤1000。這些數(shù)字表示在A和城市B中間有一條雙行道，并且在V分鐘內(nèi)是就能通過。

輸出描述 Output Description

輸出文件的第一行中寫出用分鐘表示的最長(zhǎng)時(shí)間，在這段時(shí)間中，無論哪條路在堵車，瑪麗卡應(yīng)該能夠到達(dá)麥克處，如果少于這個(gè)時(shí)間的話，則必定存在一條路，該條路一旦堵車，瑪麗卡就不能夠趕到麥克處。

樣例輸入 Sample Input

5 7 1 2 8 1 4 10 2 3 9 2 4 10 2 5 1 3 4 7 3 5 10

樣例輸出 Sample Output

27

• 這道題先跑一遍SPFA，找出 點(diǎn)1 到 點(diǎn)N 最短路的路徑，然后枚舉這條路徑上的所有邊，依次將它們的權(quán)值賦為 +∞ 然后跑一遍SPFA。答案就是 Max(disN) 了。
• 因?yàn)槿绻萝嚹菞l路不在 點(diǎn)1 到 點(diǎn)N 最短路的路徑 上時(shí)，最小時(shí)間應(yīng)該就是 點(diǎn)1 到 點(diǎn)N 的距離。

#include <cstdio> #include <deque> #define INF 1000000007 int n, m; int hu[1005], hv[1005], f[1005]; bool vis[1005]; struct edge_type {int u, v, w, nu, nv; }; edge_type edge[1000005]; int dis[1005]; std::deque<int> q; int main() {int x, y, z;scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++i){scanf("%d%d%d", &x, &y, &z);edge[i].u = x;edge[i].v = y;edge[i].w = z;edge[i].nu = hu[x];edge[i].nv = hv[y];hu[x] = i;hv[y] = i;}int tmp, now, p, ans = 0, ttmp, ei;q.clear();for (int i = 1; i <= n; ++i)dis[i] = INF;dis[1] = 0;f[1] = 0;vis[1] = true;q.push_back(1);while (!q.empty()){now = q.front();q.pop_front();vis[now] = false;p = hu[now];while (p){if (dis[edge[p].v] > dis[now] + edge[p].w){dis[edge[p].v] = dis[now] + edge[p].w;f[edge[p].v] = p;if (!vis[edge[p].v]){q.push_back(edge[p].v);vis[edge[p].v] = true;}}p = edge[p].nu;}p = hv[now];while (p){if (dis[edge[p].u] > dis[now] + edge[p].w){dis[edge[p].u] = dis[now] + edge[p].w;f[edge[p].u] = p;if (!vis[edge[p].u]){q.push_back(edge[p].u);vis[edge[p].u] = true;}}p = edge[p].nv;}}ttmp = n;ei = f[n];while(ei){tmp = edge[ei].w;edge[ei].w = INF;q.clear();for (int i = 1; i <= n; ++i)dis[i] = INF;dis[1] = 0;f[1] = 0;vis[1] = true;q.push_back(1);while (!q.empty()){now = q.front();q.pop_front();vis[now] = false;p = hu[now];while (p){if (dis[edge[p].v] > dis[now] + edge[p].w){dis[edge[p].v] = dis[now] + edge[p].w;f[edge[p].v] = p;if (!vis[edge[p].v]){q.push_back(edge[p].v);vis[edge[p].v] = true;}}p = edge[p].nu;}p = hv[now];while (p){if (dis[edge[p].u] > dis[now] + edge[p].w){dis[edge[p].u] = dis[now] + edge[p].w;f[edge[p].u] = p;if (!vis[edge[p].u]){q.push_back(edge[p].u);vis[edge[p].u] = true;}}p = edge[p].nv;}}if (ans < dis[n])ans = dis[n];edge[ei].w = tmp;ttmp = edge[ei].u ^ edge[ei].v ^ ttmp;ei = f[ttmp];}printf("%d", ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/maghsk/p/5122854.html

總結(jié)

以上是生活随笔為你收集整理的Codevs 1021 玛丽卡的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。