本文共 1401 字，大约阅读时间需要 4 分钟。

链接：https://ac.nowcoder.com/acm/contest/5026/D 来源：牛客网

题目描述

给定一个有向带权图，其中包括 n个城市，城市编号从1 到n，有向边的编号从 1 到 m，现在有一个人位于城市 1，并且想要到城市n旅游。现在政府正在决定将一条道路反向，这个人想知道在某一指定道路反向的情况到达城市n最短路径长度会不会变短。

保证开始给定的图从城市1可以到达城市n，若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短。

输入描述:

第一行包括两个整数n，m（1≤n≤100000，1≤m≤200000)

接下来m行每行三个整数u，v，c (1≤u,v≤n, 1≤c≤10^9)，分别代表一条有向边的起点，终点和边权。保证没有自环。

接下来一行一个整数q（1≤q≤200000），代表查询组数，查询之间是独立的。

接下来q行每行一个整数x（1≤x≤m），代表询问将第x条边反向后到达城市n的最短路长度会不会变短。

输出描述:

共q行，如果最短路变短输出YES，否则输出NO。 示例1 输入

3 4

1 2 100 2 3 100 3 1 100 2 1 1 2 1 4 输出

NO

YES 说明 第一条边反向后从点1无法到达点3，所以输出NO。 第四条边反向后从点1到点3的最短路长度从200减少到101，所以输出YES。 思路：不知道为什么这个题会比C过的少，明明这个题是水题呀，秒出的那种，反而是C题卡了好久，还是太菜了。 如题，换个思维想想，如果将一条边反向了会导致最短路变短的话，那个最短路就一定会经过这条反向的边，仔细想想是不是？于是我们就正向和方向建边跑spfa，spfa1起点是1，spfa2起点是n，对于一条边u->v来说，只要判断d2【u】+d1【v】+cost是否小于d1【n】即可。注意我们只要判断是否变短就可以了，至于是不是变得无法到达的情况对我们的最终判断并无影响。

#include
   
    using namespace std;typedef long long ll;const int maxn=2e5+1;const ll inf=1e18;bool vis[maxn];int x[maxn],y[maxn];ll w,d1[maxn],d2[maxn],z[maxn];vector
    
     
      >g[maxn],e[maxn];void spfa1(int x){   	memset(vis,false,sizeof(vis));	for(int i=0;i