删除某条边最短路会改变的模板

FZ3ZOJ89
  1 #include <iostream>
  2 #include <string>
  3 #include <string.h>
  4 #include <cmath>
  5 #include <stdio.h>
  6 #include <algorithm>
  7 #include <queue>
  8 #define M 210000
  9 #define N 40001
 10 using namespace std;
 11 struct node
 12 {
 13     int u,v,w;
 14 }a[M*2];
 15 struct node2
 16 {
 17     int next,num,to,w;
 18 }e[M*2];
 19 int g[M]={};
 20 int cnt=0;int n,m;
 21 int dis[2][N];
 22 int source,tss;
 23 int low[N]={};int dfn[N]={};
 24 int tle=0;
 25 bool cut[M]={};
 26 inline void add(int u,int v,int w,int faqq=0)
 27 {
 28     e[++cnt].next=g[u];
 29     g[u]=cnt;
 30     e[cnt].to=v;
 31     e[cnt].w=w;
 32     e[cnt].num=faqq;
 33 }
 34 void prework(int type)
 35 {
 36     int i;
 37     for (i=1;i<=n;i++) dis[type][i]=1000000007;
 38 }
 39 void spfa(int type)
 40 {
 41     int i;int pu;
 42     prework(type);
 43     if (type==0) pu=source;
 44     else pu=tss;
 45     queue<int> q;
 46     dis[type][pu]=0;
 47     q.push(pu);
 48     while(!q.empty())
 49       {
 50         int u=q.front();
 51         q.pop();
 52         for (i=g[u];i;i=e[i].next)
 53           if (dis[type][e[i].to]>dis[type][u]+e[i].w)
 54             {
 55             
 56               dis[type][e[i].to]=dis[type][u]+e[i].w;
 57               q.push(e[i].to);
 58             }
 59       }
 60 }
 61 void tarjan(int u,int fa)
 62 {
 63     low[u]=dfn[u]=++tle;
 64     for (int i=g[u];i;i=e[i].next)
 65       {
 66         if (e[i].to==fa) continue;
 67         if (dfn[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);
 68         else
 69           {
 70             tarjan(e[i].to,u);
 71             low[u]=min(low[u],low[e[i].to]);
 72             if (low[e[i].to]>dfn[u]) 
 73               cut[e[i].num]=1;
 74           }
 75       }
 76 }
 77 int main()
 78 {
 79     int i,j,k,l;
 80     cin>>n>>m>>source>>tss;
 81     //for (i=1;i<=n;i++) dis[1][i]=dis[0][i]=1000000007;
 82     for (i=1;i<=m;i++)
 83       {
 84         int wwd,lxy,sps;
 85         scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
 86         wwd=a[i].u;lxy=a[i].v;sps=a[i].w;
 87         add(wwd,lxy,sps);
 88         add(lxy,wwd,sps);
 89       }
 90     spfa(1);
 91     spfa(0);
 92     int lnx=dis[0][tss];
 93     //for (i=1;i<=n;i++) cout<<dis[1][i];
 94     cnt=0;memset(g,0,sizeof(g));
 95     for (i=1;i<=m;i++)
 96       if (dis[0][a[i].u]+a[i].w+dis[1][a[i].v]==lnx || dis[0][a[i].v]+a[i].w+dis[1][a[i].u]==lnx)
 97        {
 98         add(a[i].u,a[i].v,0,i);
 99         add(a[i].v,a[i].u,0,i);
100         //cout<<i;
101         
102       }
103     tarjan(source,0);
104     int q;
105     
106     cin>>q;
107     while(q--)
108       {
109         int gcy;
110         scanf("%d",&gcy);
111         if (cut[gcy]) puts("No");
112         else puts("Yes");
113       } 
114 }
233