SHARE
TWEET

Untitled

a guest May 24th, 2015 252 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include<windows.h>
  3.  
  4. #define FOR(i,a,b) for(auto i=a; i!=b+1-2*(a>b); i+=1-2*(a>b))
  5. #define REP(i,a,b) for(auto i=a-(a>b); i!=b-(a>b); i+=1-2*(a>b))
  6. #define ALL(v) v.begin(),v.end()
  7. #define what_is(x) cout<<#x<<" is "<<x<<endl;
  8. #define min3(a,b,c) min(min(a,b),c)
  9. #define max3(a,b,c) max(max(a,b),c)
  10. #define SIZE 300010
  11. #define MAXN 1000010
  12. #define PI 3.141592653589793
  13. #define open_read1 freopen("C:\\Users\\Hepic\\Desktop\\a.txt","r",stdin)
  14. #define open_write1 freopen("C:\\Users\\Hepic\\Desktop\\b.txt","w",stdout)
  15. #define open_read freopen("rblock.in","r",stdin)
  16. #define open_write freopen("rblock.out","w",stdout)
  17.  
  18. using namespace std;
  19.  
  20.  
  21. typedef long long LL;
  22. typedef pair<int,int> PII;
  23.  
  24.  
  25. struct info
  26. {
  27.     int nde,edge_id;
  28.     LL dst;
  29.  
  30.     bool friend operator < (const info &in1, const info &in2)
  31.     {
  32.         return in1.dst > in2.dst;
  33.     }
  34. };
  35.  
  36.  
  37. int N,M,A,B,stNode,cnt;
  38. int node,Tid;
  39. int conn_node,conn_id;
  40. bool visited[SIZE];
  41. LL dist,conn_dist,whole_dist,min_cost,C;
  42. LL min_dist[SIZE], edge_cost[SIZE];
  43. set<PII> keep_edges;
  44. vector<info> tree[SIZE];
  45. priority_queue<info> que;
  46.  
  47.  
  48. void dijkstra(int starting_node)
  49. {
  50.     REP(i,0,SIZE)
  51.     {
  52.         visited[i] = false;
  53.         min_dist[i] = -1;
  54.     }
  55.  
  56.     que.push( info{starting_node, -1, 0} );
  57.  
  58.  
  59.     while(!que.empty())
  60.     {
  61.         node = que.top().nde;
  62.         dist = que.top().dst;
  63.         Tid = que.top().edge_id;
  64.         que.pop();
  65.  
  66.  
  67.         if(min_dist[node] == -1  ||  dist < min_dist[node])
  68.         {
  69.             min_dist[node] = dist;
  70.  
  71.             if(Tid != -1)
  72.                 keep_edges.insert( make_pair(node, Tid) );
  73.         }
  74.  
  75.         else if(min_dist[node] == dist)
  76.         {
  77.             auto itr = lower_bound( ALL(keep_edges), make_pair(node, -1) );
  78.  
  79.             if(edge_cost[Tid] < edge_cost[itr->second])
  80.             {
  81.                 keep_edges.erase(itr);
  82.                 keep_edges.insert( make_pair(node, Tid) );
  83.             }
  84.         }
  85.  
  86.  
  87.         visited[node]=true;
  88.  
  89.  
  90.         REP(i,0,tree[node].size())
  91.         {
  92.             conn_node  = tree[node][i].nde;
  93.             conn_dist = tree[node][i].dst;
  94.             conn_id = tree[node][i].edge_id;
  95.  
  96.             whole_dist = dist + conn_dist;
  97.  
  98.             if(!visited[conn_node])
  99.                 que.push( info{conn_node, conn_id, whole_dist} );
  100.         }
  101.     }
  102. }
  103.  
  104.  
  105. int main()
  106. {
  107.     //open_read1;
  108.     scanf("%d%d",&N,&M);
  109.  
  110.     FOR(i,1,M)
  111.     {
  112.         scanf("%d%d%I64d",&A,&B,&C);
  113.  
  114.         ++cnt;
  115.  
  116.         tree[A].push_back( info{B, cnt, C} );
  117.         tree[B].push_back( info{A, cnt, C} ) ;
  118.         edge_cost[cnt] = C;
  119.     }
  120.  
  121.     scanf("%d",&stNode);
  122.  
  123.  
  124.  
  125.     dijkstra(stNode);
  126.  
  127.     for(auto val:keep_edges)
  128.         min_cost += edge_cost[val.second];
  129.  
  130.  
  131.  
  132.     printf("%I64d\n",min_cost);
  133.  
  134.     for(auto val:keep_edges)
  135.         cout<<val.second<<" ";
  136.  
  137.     printf("\n");
  138.  
  139.  
  140.     return 0;
  141. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top