Description
A国有N座城市，依次标为1到N。同时，在这N座城市间有M条单向道路，每条道路的长度是一个正整数。现在，A国交通部指定了一条从城市1到城市N的路径，并且保证这条路径的长度是所有从城市1到城市N的路径中最短的。不幸的是，因为从城市1到城市N旅行的人越来越多，这条由交通部指定的路径经常发生堵塞。现在A国想知道，这条路径中的任意一条道路无法通行时，由城市1到N的最短路径长度是多少。
Input
输入文件第一行是三个用空格分开的正整数N、M和L，分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。
按下来M行，每行三个用空格分开的整数a、b和c，表示存在一条由城市a到城市b的长度为c的单向道路。这M行的行号也是对应道路的编号，即其中第1行对应的道路编号为1，第2行对应的道路编号为2，…，第M行对应的道路编号为M。最后一行为L个用空格分开的整数sp(1)…，，sp(L)，依次表示从城市1到城市N的由交通部指定的最短路径上的道路的编号。
Output
输出文件包含L行，每行为一个整数，第i行(i=1，2…，，L)的整数表示删去编号为sp(i)的道路后从城市1到城市N的最短路径长度。如果去掉后没有从城市1到城市N的路径，则输出一1。
Sample Input
1 2 1
2 3 1
4 6 1
2 5 2
5 4 3
1 2 3 4
Sample Output
7
7
-1
HINT
100%的数据满足2<N<100000，1<M<200000。所用道路长度大于0小于10000。
这题我用的ydc的做法。。。但是不得不承认他还是太屌了。。。QAQ
首先很容易想到即使去掉一条边之后，最短路依然是pre[a]+suf[b]+dis(a,b)，其中a，b均为最短路上的点，pre指a到起点的最短路距离，b为b到终点的最短路距离，dis(a,b)为a到b的距离(不走最短路上的边)。。。
然后我就想到这里了。。。
之后就是ydc神奇做法。首先肯定还是枚举删去的边，然后从这条边的出发点开始跑spfa，不走删掉的边(注意，不要取清空dis数组，因为每个点的dis肯定是单调递减的，不然必然会TLE)。从该点跑到另一个最短路上的点p(p必须在所删的边之后)，然后把整条路径的长度和p一起加入平衡树中。出来平衡树中取出长度最小的边，若其做对应的p点(最短路)并没有在所删的边之后，该边删除。若平衡树为空，则输出-1。
不得不说这个做法很漂亮，它利用到了枚举边的单调性，反正我肯定想不到。。。。
如果实在是不懂的话，看代码，代码应该很好理解。
#include<set>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std; #define maxn (200010)
int side[maxn],toit[maxn],next[maxn],dis[maxn],pos[maxn],occ[maxn],stack[maxn];
int pre[maxn],suf[maxn],len[maxn],n,m,l,id,cnt,p[maxn],edge[maxn],val[maxn];
bool ban[maxn],in[maxn];
struct node
{
int to,val;
friend inline bool operator <(const node &a,const node &b)
{
if (a.val != b.val) return a.val < b.val;
else return pos[a.to] < pos[b.to];
}
};
multiset <node> MS; inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} inline void add(int a,int b,int c)
{
next[++cnt] = side[a]; side[a] = cnt;
toit[cnt] = b; len[cnt] = c;
} inline void spfa(int d,int source,int lim)
{
queue <int> team; int top = ;
team.push(source); dis[source] = d; ++id;
while (!team.empty())
{
int now = team.front(); team.pop();
for (int i = side[now];i;i = next[i])
{
if (ban[i]) continue;
if (pos[toit[i]] >= lim)
{
if (occ[toit[i]] != id)
occ[toit[i]] = id,stack[++top] = toit[i],val[toit[i]] = dis[now]+len[i]+suf[pos[toit[i]]];
else val[toit[i]] = min(val[toit[i]],dis[now]+len[i]+suf[pos[toit[i]]]);
}
else if (dis[toit[i]] > dis[now]+len[i])
{
dis[toit[i]] = dis[now] + len[i];
if (!in[toit[i]]) in[toit[i]] = true,team.push(toit[i]);
}
}
in[now] = false;
}
for (int i = ;i <= top;++i) MS.insert((node) {stack[i],val[stack[i]]});
} inline void work()
{
pos[] = p[] = ;
for (int i = ;i <= l;++i)
edge[i] = read(),pos[toit[edge[i]]] = i+,p[i+] = toit[edge[i]];
for (int i = ;i <= l;++i) pre[i] = pre[i-]+len[edge[i]];
for (int i = l;i;--i) suf[i] = suf[i+]+len[edge[i]];
memset(dis,0x7,*(n+)); dis[] = ;
for (int i = ;i <= l;++i)
{
ban[edge[i]] = true; spfa(pre[i-],p[i],i+); ban[edge[i]] = false;
while (!MS.empty()&&pos[MS.begin()->to]<=i) MS.erase(MS.begin());
if (MS.empty()) puts("-1");
else printf("%d\n",MS.begin()->val);
}
} int main()
{
freopen("3575.in","r",stdin);
freopen("3575.out","w",stdout);
n = read(),m = read(),l = read(); int a,b,c;
while (m--) a = read(),b = read(),c = read(),add(a,b,c);
work();
fclose(stdin); fclose(stdout);
return ;
}