Untitled
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; }