fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. // dijkistra algo
  4. // code help from https://w...content-available-to-author-only...s.org/printing-paths-dijkstras-shortest-path-algorithm/
  5. vector<long> v;
  6.  
  7. long mintime(long time[] , bool sptset[] ,long n )
  8. {
  9. long min = INT_MAX,min_index;
  10.  
  11. for(long i=0;i<n;i++)
  12. {
  13. if(sptset[i]==false && time[i] <= min)
  14. min = time[i],min_index=i;
  15. }
  16. return min_index;
  17. }
  18.  
  19. void pushpath(long parent[], long root)
  20. {
  21. //cerr<<root<<endl;
  22.  
  23. // Base Case : If j is source
  24. if (parent[root] == - 1)
  25. return;
  26.  
  27. pushpath(parent, parent[root]);
  28.  
  29. v.push_back(root);
  30. }
  31.  
  32.  
  33. long leastTimeToInterview(long n, long d, long m)
  34. {
  35. long time[n],parent[n],i,j;
  36. bool sptset[n];
  37. long graph[n][n];
  38.  
  39. for(i=0;i<n;i++)
  40. for(j=0;j<n;j++)
  41. graph[i][j]=0;
  42.  
  43. for(i=0;i<m;i++)
  44. {
  45. long x,y,t;
  46. cin>>x>>y>>t;--x;--y;
  47. graph[x][y]=t;
  48. graph[y][x]=t;
  49. }
  50. /* for(i=0;i<n;i++){
  51. for(j=0;j<n;j++)
  52. cout<<graph[i][j]<<" ";
  53. cout<<endl;
  54. }*/
  55. for(i=0;i<n;i++)
  56. {
  57. parent[0]=-1;
  58. time[i]=INT_MAX;
  59. sptset[i]=false;
  60. }
  61. time[0]=0;
  62.  
  63. for(i=0;i<n-1;i++)
  64. {
  65. long u=mintime(time,sptset,n);
  66. sptset[u]=true;
  67.  
  68. for(j=0;j<n;j++)
  69. {
  70. if(!sptset[j] && graph[u][j] && time[u] + graph[u][j] < time[j] )
  71. {
  72. parent[j] = u;
  73. time[j] = time[u] +graph[u][j];
  74. }
  75. }
  76. }
  77. v.push_back(0);
  78. pushpath(parent,n-1);
  79.  
  80. long total=0,delay=0,check=0;
  81. for(i=0;i<v.size()-1;i++)
  82. {
  83. //cerr<<" v[i] is "<<v[i]<<" v[i+1] "<<v[i+1];
  84. total+=graph[v[i]][v[i+1]];
  85. //cerr<<" total is "<<total;
  86. if( (total/d)%2 !=0 && (total/d)%2 >check)
  87. {
  88. check=(total/d)%2 ;
  89. delay+=d-(total%4);
  90. //cerr<<" delay "<<delay;
  91. }//cerr<<endl;
  92. }
  93. //cerr<<delay<<endl;
  94. total+=delay;
  95. return total;
  96. }
  97.  
  98.  
  99. int main()
  100. {
  101. long n,d,m;
  102. cin>>n>>d>>m;
  103. cout<<leastTimeToInterview( n, d, m);
  104. }
Runtime error #stdin #stdout 0s 4348KB
stdin
Standard input is empty
stdout
Standard output is empty