#include<bits/stdc++.h> using namespace std; // dijkistra algo // code help from https://w...content-available-to-author-only...s.org/printing-paths-dijkstras-shortest-path-algorithm/ vector<long> v; long mintime(long time[] , bool sptset[] ,long n ) { long min = INT_MAX,min_index; for(long i=0;i<n;i++) { if(sptset[i]==false && time[i] <= min) min = time[i],min_index=i; } return min_index; } void pushpath(long parent[], long root) { //cerr<<root<<endl; // Base Case : If j is source if (parent[root] == - 1) return; pushpath(parent, parent[root]); v.push_back(root); } long leastTimeToInterview(long n, long d, long m) { long time[n],parent[n],i,j; bool sptset[n]; long graph[n][n]; for(i=0;i<n;i++) for(j=0;j<n;j++) graph[i][j]=0; for(i=0;i<m;i++) { long x,y,t; cin>>x>>y>>t;--x;--y; graph[x][y]=t; graph[y][x]=t; } /* for(i=0;i<n;i++){ for(j=0;j<n;j++) cout<<graph[i][j]<<" "; cout<<endl; }*/ for(i=0;i<n;i++) { parent[0]=-1; time[i]=INT_MAX; sptset[i]=false; } time[0]=0; for(i=0;i<n-1;i++) { long u=mintime(time,sptset,n); sptset[u]=true; for(j=0;j<n;j++) { if(!sptset[j] && graph[u][j] && time[u] + graph[u][j] < time[j] ) { parent[j] = u; time[j] = time[u] +graph[u][j]; } } } v.push_back(0); pushpath(parent,n-1); long total=0,delay=0,check=0; for(i=0;i<v.size()-1;i++) { //cerr<<" v[i] is "<<v[i]<<" v[i+1] "<<v[i+1]; total+=graph[v[i]][v[i+1]]; //cerr<<" total is "<<total; if( (total/d)%2 !=0 && (total/d)%2 >check) { check=(total/d)%2 ; delay+=d-(total%4); //cerr<<" delay "<<delay; }//cerr<<endl; } //cerr<<delay<<endl; total+=delay; return total; } int main() { long n,d,m; cin>>n>>d>>m; cout<<leastTimeToInterview( n, d, m); }
Standard input is empty
The brand new service which powers Ideone!
Widget for compiling and running the source code in a web browser!
Home
API
Language
FAQ
Credits
desktop
mobile
Terms of Service
Privacy Policy
GDPR Info
Popular languages:
Bash
Pascal
C
Perl
C#
PHP
C++
Python
C++14
Python3
Haskell
Ruby
Java
SQLite
Objective-C
Swift
VB.net
List of all supported programming languages