fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define pill pair<int,ll>
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define ff fi.fi
  12. #define fs fi.se
  13. #define sf se.fi
  14. #define ss se.se
  15. #define MASK(x) (((1)<<(x))-1)
  16. #define getbit(x,k) (((x)>>(k))&1)
  17.  
  18. using namespace std;
  19.  
  20. const int maxn=3e4+5,mod=1e17+9;
  21. const ll inf=0x3f3f3f3f3f3f3f3f;
  22.  
  23. int n,m;
  24. vector<pii>eg[maxn];
  25. ll d[maxn],w1[maxn],w2[maxn];
  26. vector<int>tv[maxn];
  27. void dijkstra(int st, ll w[])
  28. {
  29.     memset(d,0x3f,sizeof d);d[st]=0;
  30.     priority_queue<pll,vector<pll>,greater<pll>>pQ;
  31.     pQ.push({d[st],st});
  32.     w[st]=1;
  33.     while(pQ.size())
  34.     {
  35.         pll u=pQ.top();pQ.pop();
  36.         if(u.fi!=d[u.se]) continue;
  37.         for(pii v:eg[u.se])
  38.         {
  39.             if(u.fi+v.se<d[v.fi])
  40.             {
  41.                 d[v.fi]=u.fi+v.se;
  42.                 w[v.fi]=w[u.se];
  43.                 if(st==1)
  44.                 {
  45.                     tv[v.fi].clear();
  46.                     tv[v.fi].pb(u.se);
  47.                 }
  48.                 pQ.push({d[v.fi],v.fi});
  49.             }
  50.             else if(u.fi+v.se==d[v.fi])
  51.             {
  52.                  w[v.fi]=(w[v.fi]+w[u.se])%mod;
  53.                  if(st==1) tv[v.fi].pb(u.se);
  54.             }
  55.         }
  56.     }
  57. }
  58. ll nad(ll a, ll b)
  59. {
  60.     ll res=0;
  61.     while(b)
  62.     {
  63.         if(b&1) res=(res+a)%mod;
  64.         a=(a+a)%mod;
  65.         b>>=1;;
  66.     }
  67.     return res;
  68. }
  69. bool P[maxn],C[maxn];
  70. void dfs(int u)
  71. {
  72.     P[u]=1;
  73.     for(int v:tv[u]) if(!P[v]) dfs(v);
  74. }
  75. int main()
  76. {
  77.     fastio
  78.     cin>>n>>m;
  79.     for(int i=1;i<=m;i++)
  80.     {
  81.         int u,v,c;cin>>u>>v>>c;
  82.         eg[u].pb({v,c});eg[v].pb({u,c});
  83.     }
  84.     dijkstra(1,w1);dijkstra(n,w2);
  85.     dfs(n);
  86.     int cnt=0;
  87.     for(int i=2;i<n;i++)
  88.     {
  89.         if(P[i])
  90.         if(nad(w1[i],w2[i])==w1[n])
  91.             cnt++,C[i]=1;
  92.     }
  93.     cout<<n-2-cnt<<'\n';
  94.     for(int i=2;i<n;i++)
  95.         if(!C[i]) cout<<i<<'\n';
  96. }
  97. /*
  98. 6 8
  99. 1 2 2
  100. 1 3 2
  101. 3 4 1
  102. 2 4 4
  103. 4 5 1
  104. 2 5 2
  105. 2 6 2
  106. 5 6 0
  107. */
  108.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-2
https://ideone.com/UMlvnr
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!