备战Noip2018模拟赛11（B组）T3 Monogatari 物语

10月27日备战Noip2018模拟赛11（B组）

T3 Monogatari物语

题目描述

某一天，少年邂逅了一见钟情的IA。见面后，IA一把牵起少年的手，决定和他一起逃离部落，离开这个无法容身的是非之地。

    要逃离部落，少年和IA就需要先选择一条耗时最少的路线，从而避免被部落的大人们抓到。部落可以大致分为Ñ个区域，少年和IA在区域1中，部落的出口设在区域N.此外部落还有中号条连接两个区域道路。道路是无向的，没有一条道路的两端连接相同的区域，也没有两条道路所连接的两个区域完全相同。对于其中前（M -1）条道路，其通过时间是确定的，但最后一条道路，由于地理因素，通过其的时间会不断变化。

现在，少年和IA得知了在K个不同的时段里，通过第M条道路的时间，请您分别计算出在这K个时段中逃离部落的最少时间，以帮助他们确定行动的时刻

输入格式

第一行三个整数N，M，K，分别表示区域数，道路数，询问数。

    接下来的M-1行每行三个整数UI，VI，WI（UI≠VI，1≤ui，vi≤N，0 <wi≤10^ 9），表示这条道路连接的区域和通过时间。

    紧接着是两个整数的ui，六（UI≠VI，1≤ui，vi≤N），表示第中号条道路连接的区域。

    最后ķ行，每行一个正整数XI（0 <xi≤10^ 9），表示目前第中号条道路的通过时间。

输出格式

输出共计ķ行，每行一个整数，表示对应时段逃离部落的最短时间。如果在该时段内无法逃离，输出“+ Inf文件”。

输入样例

4 5 4
1 2 7
1 3 4
2 4 3
3 4 6
2 3
1
2
4
6

输出样例

8
9
10
10

样例解释

如图1，红色的圆圈表示少年和IA的出发地，绿色的圆圈表示目的地，连线表示道路，旁边的数字表示通过该道路的时间。最后一条道路时间未知用X表示。

图中不重复经过同一区域的路径有4条，分别为1→2→4,1→3→4,1→2→3→4,1→3→2→4，其所需时间随X的关系如下表所示

可以证明，不存在更优的解，故将上表最后一列输出。

数据范围

思路

这个数据范围猛一看真的很恶心啊

（1）对于每一次变化，我们都可以用SPFA来求出1 - n的最短路，那这样的复杂度就是，也是会tle的

（2）那么可以把（1）的方法稍微改进一下，用样例的情况举例，只要用两次SPFA，

1. 将最后一条通过时间不确定的道路当做不连通
2. 第一次SPFA求出1到其他点的最短路用dis1 []表示
3. 第二次SPFA求出4到其他点的最短路用dis2 []表示
4. 最短路= min（dis1 [2] + x + dis2 [3]，dis2 [2] + x + dis1 [3]，dis1 [4]）

这样子的复杂度就变成了

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int MAXN = 2e5 + 5; 
const int MAXM = 5e5 + 5; 
const long long INF = 0x7fffffffffffffffll / 3; struct Data{long long x;int y;bool operator < (const Data &a) const{return a.x < x;}
};struct Node{int frm, nxt, to, dst;
}a[MAXM * 2];priority_queue <Data> Q;int n, m, k, U, V, numEdge;
int vis[MAXN], head[MAXN];
long long dis1[MAXN], dis2[MAXN];inline int read ();
inline void addEdge (int u, int v, int w);
inline void SPFA (int start);int main ()
{freopen("monogatari.in", "r", stdin); freopen("monogatari.out", "w", stdout); int u, v, w;n = read (), m = read (), k = read ();for (int i = 1; i < m ; ++ i){u = read (), v = read (), w = read ();addEdge (u, v, w);addEdge (v, u, w);}U = read (), V = read ();SPFA (1);memcpy (dis1, dis2, sizeof (dis1));            //保存前一次求出的最短路SPFA (n);for (int i = 1; i <= k; ++ i){int d = read ();long long ans = min (dis1[n], min (dis1[U] + d + dis2[V], dis2[U] + d + dis1[V]));if (ans >= INF) printf ("+Inf\n");else printf ("%lld\n", ans);}fclose (stdin);fclose (stdout);return 0;
}inline int read ()
{char ch = getchar ();int f = 1;while (!isdigit (ch)) {if (ch == '-') f = -1;ch = getchar ();}int x = 0;while (isdigit (ch)) {x = x * 10 + ch - '0';ch = getchar ();}return x * f;
}inline void addEdge (int u, int v, int w)
{++ numEdge;a[numEdge].dst = w;a[numEdge].to = v;a[numEdge].nxt = head[u];head[u] = numEdge;return ;
}inline void SPFA (int start)
{fill (dis2, dis2 + MAXN, INF);Data tmp;tmp.x = 0;tmp.y = start;Q.push (tmp);vis[start] = true;dis2[start] = 0;do{int u = Q.top ().y;int t = Q.top ().x;Q.pop ();if (t > dis2[u]) continue;for (int i = head [u]; i; i = a[i].nxt){int v = a[i].to;if (dis2[v] > dis2[u] + a[i].dst){dis2[v] = dis2[u] + a[i].dst;tmp.x = dis2[v];tmp.y = v;Q.push (tmp);}}}while (!Q.empty ());
}