P2296-寻找道路

我会带着你远行 2023-06-01 08:58 87阅读 0赞

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 #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 y,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,1,E+1)
    103     {
    104         int a = read();
    105         int b = read();
    106         add(a,b,1);
    107         add1(b,a,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     else
    124         printf("%d\n",d[ed]);
    125     return 0;
    126 }

转载于:https://www.cnblogs.com/Asurudo/p/11617272.html