备战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

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

    最后ķ行，每行一个正整数XI（0

输出格式

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

输入样例

#include 
#include 
#include 
#include 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  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 ());
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！