fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME "CENTER"
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)3e4 + 5;
  6. const int LIM = (int)1e5 + 1;
  7. const long long MOD = (long long)1e13 + 15092007;
  8. #define xd '\n' 
  9. #define fi first
  10. #define se second
  11. const long long base = (long long)256;
  12. const long long INF = (long long)1e12;
  13. template<class X, class Y> bool minimize(X &a, Y b) {if(a>b){a=b;return true;}return false;};
  14. template<class X, class Y> bool maximize(X &a, Y b) {if(a<b){a=b;return true;}return false;};
  15.  
  16. void HuuThien() {
  17.     ios_base::sync_with_stdio(0);
  18.     cin.tie(0); cout.tie(0);    
  19.     if (fopen(FNAME".inp", "r")) {
  20.         freopen(FNAME".inp", "r", stdin);
  21.         freopen(FNAME".out", "w", stdout);
  22.     }
  23. }
  24.  
  25. int n, m;
  26. vector<long long> d1(MAXN, INF), d2(MAXN, INF), c1(MAXN, 0), c2(MAXN, 0);
  27.  
  28. struct Node{
  29.     int u, w;
  30. };
  31.  
  32. vector<Node> adj[MAXN];
  33.  
  34. void Init() {
  35.     cin >> n >> m;
  36.  
  37.     for(int i = 1; i <= m ; i++) {
  38.         int u, v, w;
  39.         cin >> u >> v >> w;
  40.         adj[u].push_back({v, w});
  41.         adj[v].push_back({u, w});
  42.     }
  43. }
  44.  
  45. void Dijkstra(int s, int choose) {
  46.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  47.  
  48.     if(choose == 1) {
  49.         d1[s] = 0;
  50.         c1[s] = 1;
  51.         pq.push({0, s});
  52.     } else {
  53.         d2[s] = 0;
  54.         c2[s] = 1;
  55.         pq.push({0, s});
  56.     }
  57.  
  58.     while(!pq.empty()) {
  59.         pair<int, int> top = pq.top();
  60.         pq.pop();
  61.  
  62.         int u = top.second;
  63.         int dis = top.first;
  64.  
  65.         if(choose == 1) {
  66.             if(dis > d1[u]) continue;
  67.         } else {
  68.             if(dis > d2[u]) continue;
  69.         }
  70.  
  71.         for(Node e : adj[u]) {
  72.             int v = e.u;
  73.             int w = e.w;
  74.             if(choose == 1) {
  75.                 if(d1[v] > d1[u] + w) {
  76.                     d1[v] = d1[u] + w;
  77.                     c1[v] = c1[u];
  78.                     pq.push({d1[v], v});
  79.                 } else if(d1[v] == d1[u] + w) {
  80.                     c1[v] += c1[u];
  81.                 }
  82.             } else {
  83.                 if(d2[v] > d2[u] + w) {
  84.                     d2[v] = d2[u] + w;
  85.                     c2[v] = c2[u];
  86.                     pq.push({d2[v], v});
  87.                 } else if(d2[v] == d2[u] + w) {
  88.                     c2[v] += c2[u];
  89.                 }
  90.             }
  91.         }
  92.  
  93.     }
  94.  
  95. }
  96.  
  97. void Solve() {
  98.     Dijkstra(1, 1);
  99.     Dijkstra(n, 2);
  100.  
  101.     int res = 0;
  102.  
  103.     vector<int> ans;
  104.     for(int i = 1; i <= n ; i++) {
  105.         if((d1[i] + d2[i] != d1[n]) || ((c1[i] * c2[i]) != c1[n] && (d1[i] + d2[i]) == d1[n])) {
  106.             res++;
  107.             ans.push_back(i);
  108.         }
  109.     }
  110.  
  111.     cout << res << xd;
  112.  
  113.     for(int x : ans) {
  114.         cout << x << xd;
  115.     }
  116. }
  117.  
  118. signed main() {
  119.     HuuThien();
  120.     Init();
  121.     Solve();
  122.     return 0;
  123. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/t4YVi8
language:
C++ (gcc 8.3)
created:
2 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!