fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define REP(i, a, b) for (int i = a; i <= b; i++)
  5. #define BACK(i, a, b) for (int i = a; i >= b; i--) 
  6. #define MOD 1000000007
  7. #define PI 4 * atan(1)
  8. #define sz(A) (int)A.size()
  9. typedef long long ll;
  10. typedef vector<int> vi;
  11. typedef pair<int, int> pii;
  12. typedef vector<long long> vll;
  13. typedef long int int32;
  14. typedef unsigned long int uint32;
  15. typedef long long int int64;
  16. typedef unsigned long long int uint64;
  17. int n,s,t,x;
  18. void solve(int test){
  19.     freopen("DN.INP", "r", stdin);
  20.     freopen("DN.OUT", "w", stdout);
  21.     cin >> n >> s >> t;
  22.     vector<pair<int,int>> adj[104];
  23.     for(int i=1; i<=n; i++){
  24.         for(int j=1; j<=n; j++){
  25.             cin >> x;
  26.             if(x != 0 && x != 10000){
  27.                 adj[i].push_back({j, x});
  28.             }
  29.         }
  30.     }
  31.     vector<int> truoc(n+1, -1);
  32.     vector<int> dist(n+1, 1e8);
  33.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  34.     dist[s] = 0;
  35.     pq.push({0, s});
  36.     while(!pq.empty()){
  37.         int u = pq.top().second;
  38.         pq.pop();
  39.         for(auto p: adj[u]){
  40.             int v = p.first;
  41.             int w = p.second;
  42.             if(dist[v] >  dist[u] + w){
  43.                 dist[v] = dist[u] + w;
  44.                 truoc[v] = u;
  45.                 pq.push({dist[v],  v});
  46.             } 
  47.         }
  48.     }
  49.     if(truoc[t] == -1){
  50.         cout << 0;
  51.     }else{
  52.         vector<int> res;
  53.         int o = t;
  54.         while(o != s){
  55.             res.push_back(o);
  56.             o = truoc[o];
  57.         }
  58.         res.push_back(s);
  59.         cout << dist[t] << "\n";
  60.         for(int i=res.size()-1; i >=0; i--){
  61.             cout << res[i] << " ";
  62.         }
  63.     }
  64.  
  65. }   
  66. int main(){
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69.     cout.tie(NULL);
  70.     int typetest = 0;
  71.     if (typetest){
  72.         int t;
  73.         cin >> t;
  74.         cin.ignore();
  75.         REP(i, 1, t){
  76.             solve(i);
  77.         }
  78.     }
  79.     else solve(0);
  80. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3ThLFu
language:
C++14 (gcc 8.3)
created:
5 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!