Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
2.1 kB
4
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 3e5+7;
const ll inf  = 1e18;

#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define pb(x) push_back(x)
#define all(x) sort(x.begin() , x.end())

void dbg(){
     cerr << endl;
}

template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)

ll dis[maxn], edge[maxn] , sum;
bool seen[maxn];
int par[maxn] , n , m , st;
map<pair<int,int>,int> mp;
vector<pair<int,int>> adj[maxn];
vector<int> vec;

void dijkstra(){
     fill(par , par + maxn , -1);
     fill(dis , dis + maxn , inf);
     fill(edge , edge + maxn , inf);
     dis[st] = 0;
     set<pair<int,int>> s;
     s.insert({0 , st});
     while(!s.empty()){
          int v = (*(s.begin())).second;
          s.erase(s.begin());
          if(seen[v]){
               continue;
          }
          seen[v] = true;
          ll d 
          for(auto [w , u] : adj[v]){
               if(dis[u] > dis[v] + w){
                    dis[u] = dis[v] + w;
                    s.insert({dis[u] , u});
                    edge[u] = w;
                    d = mp[{v , u}];
               }
               else if(dis[u] == (dis[v] + w)){
                    if(edge[u] > w){
                         d = mp[{u , v}];
                         edge[u] = w;
                    }
               }
          }
     if(edge[v] < inf){
          sum += edge[v];
          vec.push_back(d);
     }
   }
}

void last(){
     cout << sum << '\n';
     for(auto pr : vec) cout << pr + 1 << ' ';
}

int main(){
     cin >> n >> m;
     for(int i = 0 ; i < m ; i++){
          int u , v, w;
          cin >> u >> v >> w;
          --u;--v;
          adj[u].push_back({w , v});
          adj[v].push_back({w , u});
          mp[{u , v}] = mp[{v , u}] = i;
     }
     cin >> st;
     st--;
     dijkstra();
     last();
     return 0;
}