fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. template<class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
  9. bool ckmin(int &u, int v) {
  10.     if (u > v) return u = v, 1;
  11.     return 0;
  12. }
  13.  
  14. void doing(int a) {
  15.     a = 2;
  16.     cout << a;
  17. }
  18.  
  19.  
  20. const int N = 2e5 + 5;
  21. const int inf = 1e18;
  22. using pii = pair<int, int>;
  23. int n, m, ans = inf;
  24.  
  25. struct Edge {
  26.     int v, w, id;
  27. };
  28. vector<Edge> G[N];
  29.  
  30.  
  31. bool on[N];
  32. vector<int> path, ansPath;
  33.  
  34. void Try(int u, int type, int sum) {
  35.     // cerr << u << " " << type << " " << sum << "\n";
  36.     if (type == 1 && u == n) type = 2;
  37.     if (type == 2 && u == 1) {
  38.         if (ckmin(ans, sum)) ansPath = path;
  39.         return;
  40.     }
  41.  
  42.     for (Edge item: G[u]) {
  43.         if (on[item.id] == 0) {
  44.             on[item.id] = 1;
  45.             path.push_back(item.v);
  46.             Try(item.v, type, sum + item.w);
  47.             on[item.id] = 0;
  48.             path.pop_back();
  49.  
  50.         }
  51.     }
  52. }
  53.  
  54.  
  55. signed main() {
  56.     cin.tie(NULL)->sync_with_stdio(false);
  57.     if(ifstream("WALK.inp")) {
  58.         freopen("WALK.inp", "r", stdin);
  59.         freopen("WALK.out", "w", stdout);
  60.     }
  61.     cin >> n >> m;
  62.     for (int i = 1; i <= m; i++) {
  63.         int u, v, w;
  64.         cin >> u >> v >> w;
  65.         G[u].push_back({v, w, i});
  66.         G[v].push_back({u, w, i});
  67.     }
  68.     path = {1};
  69.     Try(1, 1, 0);
  70.     if (ans == inf) cout << -1;
  71.     else {
  72.         cout << ans << "\n";
  73.         for (int item: ansPath) cout << item << " ";
  74.     }
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 8236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/D0kjAW
language:
C++14 (gcc 8.3)
created:
16 hours 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!