fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 30001;
  5. const int INF = 1e18;
  6. int n, m;
  7. vector<pair<int, int> > g[maxn];
  8. vector<int> d1(maxn, INF);
  9. vector<int> dn(maxn, INF);
  10. vector<int> cnt1(maxn, 0);
  11. vector<int> cnt2(maxn, 0);
  12. vector<int> ans;
  13. void dijkstra(int s, vector<int> &d, vector<int> &cnt){
  14.     priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
  15.     pq.push({0, s});
  16.     d[s] = 0;
  17.     cnt[s] = 1;
  18.     while(!pq.empty()){
  19.         pair<int, int> node = pq.top(); pq.pop();
  20.         int u = node.second;
  21.         int kc = node.first;
  22.         if(kc > d[u]) continue;
  23.         for(auto &it : g[u]){
  24.             int v = it.first;
  25.             int kcv = it.second;
  26.             if(d[v] > d[u] + kcv){
  27.                 cnt[v] = cnt[u];
  28.                 d[v] = d[u] + kcv;
  29.                 pq.push({d[v], v});
  30.             }
  31.             else if(d[v] == d[u] + kcv){
  32.                 cnt[v] += cnt[u];
  33.             }
  34.         }
  35.     }
  36. }
  37. void solve(){
  38.     cin >> n >> m;
  39.     for(int i = 0; i < m; i++){
  40.         int u, v, d; cin >> u >> v >> d;
  41.         g[u].push_back({v, d});
  42.         g[v].push_back({u, d});
  43.     }
  44.     dijkstra(1, d1, cnt1);
  45.     dijkstra(n, dn, cnt2);
  46.     int shortest = d1[n];
  47.     for(int i = 2; i < n; i++){
  48.         if(d1[i] + dn[i] > shortest || (d1[i] + dn[i] == shortest && cnt1[i] * cnt2[i] < cnt1[n])){
  49.             ans.push_back(i);
  50.         }
  51.     }
  52.     sort(ans.begin(), ans.end());
  53.     cout << ans.size() << endl;
  54.     for(auto x : ans){
  55.         cout << x << endl;
  56.     }
  57. }
  58. signed main()
  59. {
  60.     solve();
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/mnd76W
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!