[日常训练]school

Description

众所周知， [日常训练]school 家离学校很远。于是，每天算准了时间出发，以保证能在上课铃响前秒到达学校。
不幸的是，市最近正在修路。这就导致有些路可能无法通行，因而可能导致迟到。
不打算改变他的出发时间，现在他告诉你他通过每一条路的时间，他想要知道如果某条路被维修了，那么他是否能避免迟到？

Input

第一行输入两个正整数 [日常训练]school ，分别表示点数(路口)和边数(路)。
第二行输入两个正整数，表示家标号为，学校标号为。
接下来行，每行三个整数，表示有一条连接的道路，走过该路所需的时间为。
接下来一个整数，表示询问的个数。
最后 [日常训练]school 行，每行一个正整数，表示询问若第条边正在维修，是否能按时到校。

Output

输出 [日常训练]school 行。
对于每一个询问，若能准时到校输出一行一个字符串,否则输出.

(字符串严格匹配，不含双引号)

Sample Input

8 11

1 8

1 2 3

1 3 1

2 3 1

2 4 5

2 5 1

4 5 4

3 5 2

5 6 4

6 7 5

6 8 2

7 8 5

Sample Output

No
Yes
No
Yes
No

HINT

[日常训练]school ,保证源点到任意点的最短路长度不超过。

Solution

先求出 [日常训练]school 到最短路的副图.如果一条边是副图的割边,那么无法避免迟到.

#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 40005
#define M 400005
using namespace std;
typedef long long ll;
struct graph{
    int nxt,to,n;ll w;
}e[M],e1[M];
ll dis[N];
int g[N],g1[N],dfn[N],low[N],n,m,s,t,cnt;
bool b[M],f[N],inq[N];
queue<int> q;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline void adde(int i,int x,int y){
    e1[++cnt].nxt=g1[x];g1[x]=cnt;
    e1[cnt].to=y;e1[cnt].n=i;
}
inline void addedge(int i,int x,int y,int z){
    e[++cnt].nxt=g[x];g[x]=cnt;
    e[cnt].to=y;e[cnt].w=(ll)(z);e[cnt].n=i;
}
inline void spfa(int u){
    for(int i=1;i<=n;++i)
        dis[i]=(ll)(1e+7);
    q.push(u);dis[u]=0;inq[u]=true;
    while(!q.empty()){
        u=q.front();q.pop();inq[u]=false;
        for(int i=g[u];i;i=e[i].nxt)
            if(dis[e[i].to]<0||dis[u]+e[i].w<dis[e[i].to]){
                dis[e[i].to]=dis[u]+e[i].w;
                if(!inq[e[i].to]){
                    q.push(e[i].to);inq[e[i].to]=true;
                }
            }
    }
}
inline void bfs(int u){
    memset(inq,0,sizeof(inq));
    cnt=0;q.push(u);inq[u]=true;
    while(!q.empty()){
        u=q.front();q.pop();
        for(int i=g[u];i;i=e[i].nxt)
            if(dis[e[i].to]+e[i].w==dis[u]){
                adde(e[i].n,e[i].to,u);adde(e[i].n,u,e[i].to);
                if(!inq[e[i].to]){
                    q.push(e[i].to);inq[e[i].to]=true;
                }
            }
    }
}
inline void tarjan(int u,int f){
    dfn[u]=low[u]=++cnt;
    for(int i=g1[u];i;i=e1[i].nxt)
        if(!dfn[e1[i].to]){
            tarjan(e1[i].to,u);
            low[u]=min(low[u],low[e1[i].to]);
            if(low[e1[i].to]>dfn[u]) b[e1[i].n]=true; 
        }
        else if(e1[i].to!=f)
            low[u]=min(low[u],dfn[e1[i].to]);
}
inline void init(){
    n=read();m=read();
    s=read();t=read();
    for(int i=1,x,y,z;i<=m;++i){
        x=read();y=read();z=read();
        addedge(i,x,y,z);addedge(i,y,x,z);
    }
    spfa(s);bfs(t);tarjan(s,0);
    int q=read();
    while(q--){
        if(b[read()]) puts("No");
        else puts("Yes");
    }
}
int main(){
    freopen("school.in","r",stdin);
    freopen("school.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

[日常训练]school

相关推荐