fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const long long INF = 4e18;
  7. const int N = 300000 + 5;
  8.  
  9. struct Edge{
  10.     int to,w,id;
  11. };
  12.  
  13. int n,m,k;
  14. vector<Edge> adj[N];
  15. long long dista[N];
  16. bool vis[N];
  17.  
  18. vector<int> ans;
  19.  
  20. signed main(){
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     cin>>n>>m>>k;
  25.  
  26.     for(int i=1;i<=m;i++){
  27.         int u,v,w;
  28.         cin>>u>>v>>w;
  29.         adj[u].push_back({v,w,i});
  30.         adj[v].push_back({u,w,i});
  31.     }
  32.  
  33.     for(int i=1;i<=n;i++) dista[i]=INF;
  34.  
  35.     priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
  36.     dista[1]=0;
  37.     pq.push({0,1});
  38.  
  39.     while(!pq.empty()){
  40.         auto [d,u]=pq.top();
  41.         pq.pop();
  42.         if(d!=dista[u]) continue;
  43.         for(auto e:adj[u]){
  44.             if(dista[e.to]>d+e.w){
  45.                 dista[e.to]=d+e.w;
  46.                 pq.push({dista[e.to],e.to});
  47.             }
  48.         }
  49.     }
  50.  
  51.     queue<int> q;
  52.     q.push(1);
  53.     vis[1]=1;
  54.  
  55.     while(!q.empty() && (int)ans.size()<k){
  56.         int u=q.front();
  57.         q.pop();
  58.  
  59.         for(auto e:adj[u]){
  60.             int v=e.to;
  61.             if(!vis[v] && dista[u]+e.w==dista[v]){
  62.                 vis[v]=1;
  63.                 ans.push_back(e.id);
  64.                 q.push(v);
  65.                 if((int)ans.size()==k) break;
  66.             }
  67.         }
  68.     }
  69.  
  70.     cout<<ans.size()<<"\n";
  71.     for(int x:ans) cout<<x<<" ";
  72. }
Success #stdin #stdout 0.01s 11948KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FWbKjb
language:
C++14 (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!