fork download
copy 
  1. // author : anphung
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define int64 long long
  6. const int64 INF = (int64)4e18;
  7. const int MOD1 = 1000000007;
  8. const int MOD2 = 1000000009;
  9.  
  10. int n, m;
  11. vector<pair<int,int>> adj[300005];
  12. int64 d1[300005], dn[300005];
  13.  
  14. void dijkstra(int s, int64 d[]){
  15.     fill(d+1, d+n+1, INF);
  16.     priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<>> pq;
  17.     d[s] = 0;
  18.     pq.push({0, s});
  19.     while(!pq.empty()){
  20.         long long du = pq.top().first;
  21.         int u = pq.top().second;
  22.         pq.pop();
  23.         if(du != d[u]) continue;
  24.         for(auto &p: adj[u]){
  25.             int v = p.first;
  26.             long long w = p.second;
  27.             if(d[v] > du + w){
  28.                 d[v] = du + w;
  29.                 pq.push({d[v], v});
  30.             }
  31.         }
  32.     }
  33. }
  34.  
  35. int main(){
  36.     ios::sync_with_stdio(0);
  37.     cin.tie(0);
  38.  
  39.     cin >> n >> m;
  40.     for(int i=0;i<m;i++){
  41.         int u,v,w;
  42.         cin >> u >> v >> w;
  43.         adj[u].push_back({v,w});
  44.         adj[v].push_back({u,w});
  45.     }
  46.  
  47.     dijkstra(1, d1);
  48.     dijkstra(n, dn);
  49.  
  50.     int64 D = d1[n];
  51.  
  52.     vector<vector<int>> dag(n+1);
  53.     vector<int> indeg(n+1, 0);
  54.  
  55.     for(int u=1;u<=n;u++){
  56.         for(auto &p: adj[u]){
  57.             int v = p.first; long long w = p.second;
  58.             if(d1[u] + w + dn[v] == D){
  59.                 dag[u].push_back(v);
  60.                 indeg[v]++;
  61.             }
  62.         }
  63.     }
  64.  
  65.     vector<int> topo;
  66.     queue<int> q;
  67.     for(int i=1;i<=n;i++){
  68.         if(indeg[i]==0) q.push(i);
  69.     }
  70.     while(!q.empty()){
  71.         int u = q.front(); q.pop();
  72.         topo.push_back(u);
  73.         for(int v: dag[u]){
  74.             if(--indeg[v]==0) q.push(v);
  75.         }
  76.     }
  77.  
  78.     vector<int> c1(n+1,0), c2(n+1,0);
  79.     c1[1] = c2[1] = 1;
  80.  
  81.     for(int u: topo){
  82.         for(int v: dag[u]){
  83.             c1[v] = (c1[v] + c1[u]) % MOD1;
  84.             c2[v] = (c2[v] + c2[u]) % MOD2;
  85.         }
  86.     }
  87.  
  88.     vector<int> d1n(n+1,0), d2n(n+1,0);
  89.     d1n[n] = d2n[n] = 1;
  90.  
  91.     reverse(topo.begin(), topo.end());
  92.     for(int u: topo){
  93.         for(int v: dag[u]){
  94.             d1n[u] = (d1n[u] + d1n[v]) % MOD1;
  95.             d2n[u] = (d2n[u] + d2n[v]) % MOD2;
  96.         }
  97.     }
  98.  
  99.     int total1 = c1[n], total2 = c2[n];
  100.  
  101.     vector<int> ans;
  102.     for(int i=2;i<n;i++){
  103.         if( (int64)c1[i]*d1n[i]%MOD1 == total1 &&
  104.             (int64)c2[i]*d2n[i]%MOD2 == total2 ){
  105.             continue; 
  106.         }
  107.         ans.emplace_back(i);
  108.     }
  109.  
  110.     cout << ans.size() << '\n';
  111.     for(int x: ans) cout << x << '\n';
  112. }
  113.  
Success #stdin #stdout 0.01s 14012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/796lce
language:
C++14 (gcc 8.3)
created:
1 day 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!