P2296-寻找道路_C

概述1 #include <bits/stdc++.h> 2 #define _for(i,a,b) for(int i = (a);i < b;i ++) 3 #define _rep(i,a,b) for(int i = (a);i > b;i --) 4 #define INF 0x3f3f3f3f 5 #define MOD 1000000007 6 #defin

  1 #include <bits/stdc++.h>  2 #define _for(i,a,b) for(int i = (a);i < b;i ++)  3 #define _rep(i,b) for(int i = (a);i > b;i --)  4 #define INF 0x3f3f3f3f  5 #define MOD 1000000007  6 #define maxn 200003  7 typedef long long ll;  8   9 using namespace std; 10 typedef pair<int,int> P;//first 是最短距离，second 是顶点编号 11 inline ll read() 12 { 13     ll ans = 0; 14     char ch = getchar(),last = ‘ ‘; 15     while(!isdigit(ch)) last = ch,ch = getchar(); 16     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘,ch = getchar(); 17     if(last == ‘-‘) ans = -ans; 18     return ans; 19 } 20 inline voID write(ll x) 21 { 22     if(x < 0) x = -x,putchar(‘-‘); 23     if(x >= 10) write(x / 10); 24     putchar(x % 10 + ‘0‘); 25 } 26 int V,E; 27 int st,ed; 28 int ver[maxn],Next[maxn],head[maxn],val[maxn]; 29 int ver1[maxn],Next1[maxn],head1[maxn],val1[maxn]; 30 int novis[maxn]; 31 int cango[maxn]; 32 int vis[maxn]; 33 int tot = 0,tot1 = 0; 34 voID add(int x,int y,int w) 35 { 36     ver[++tot] = y,Next[tot] = head[x],head[x] = tot,val[tot] = w; 37 } 38 voID add1(int x,int w) 39 { 40     ver1[++tot1] = y,Next1[tot1] = head1[x],head1[x] = tot1,val1[tot1] = w; 41 } 42 int d[maxn]; 43 voID shortest_path(int s) 44 { 45     priority_queue<P,vector<P>,greater<P>> que; 46  47     _for(i,1,V+1) 48     d[i] = INF; 49     d[s] = 0; 50     que.push(P {0,s}); 51  52     while(!que.empty()) 53     { 54         P p = que.top(); 55         que.pop(); 56         int v = p.second; 57         if(novis[v] || d[v] < p.first) continue; 58         for(int i = head[v]; i; i = Next[i]) 59         { 60             int y = ver[i]; 61             int w = val[i]; 62             if(d[y] > d[v] + w) 63             { 64                 d[y] = d[v] + w; 65                 que.push(P {d[y],y}); 66             } 67         } 68     } 69 } 70  71 bool dfs(int s) 72 { 73     cango[s] = 1; 74     for(int i = head1[s]; i; i = Next1[i]) 75     { 76         int y = ver1[i]; 77         if(!vis[y]) 78         { 79             vis[y] = 1; 80             dfs(y); 81         } 82     } 83 } 84 bool dfs2(int s) 85 { 86     for(int i = head[s]; i; i = Next[i]) 87     { 88         int y = ver[i]; 89         if(!cango[y]) 90             novis[s] = 1; 91         if(!vis[y]) 92         { 93             vis[y] = 1; 94             dfs2(y); 95         } 96     } 97 } 98 int main() 99 {100 //    freopen("testdata.in","r+",stdin);101     V = read(),E = read();102     _for(i,E+1)103     {104         int a = read();105         int b = read();106         add(a,b,1);107         add1(b,1);108     }109     st = read();110     ed = read();111     dfs(ed);112     memset(vis,0,sizeof(vis));113     dfs2(st);114 /*115     printf("\n");116     _for(i,1,V+1)117     printf("%d %d %d\n",i,novis[i],cango[i]);118 */119     120     shortest_path(st);121     if(d[ed]==INF)122         printf("%d\n",-1);123     else124         printf("%d\n",d[ed]);125     return 0;126 }