Submission #114312

#TimeUsernameProblemLanguageResultExecution timeMemory
114312MohamedAhmed04Ceste (COCI17_ceste)C++14
64 / 160
219 ms16240 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 110 , MAXT = MAXN * MAXN; struct edge { int to , time , cost ; edge(int ve , int ti , int co) { to = ve ; time = ti ; cost = co ; } }; vector< vector<edge> >adj(MAXN) ; long long dp[MAXN][MAXT] ; long long ans[MAXN] ; int vis[MAXN][MAXT] ; int tellnow[MAXN] ; int n , m ; int readint() { bool minus = false; int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = getchar(); } if (ch == '-') minus = true; else result = ch-'0'; while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; result = result*10 + (ch - '0'); } if (minus) return -result; else return result; } int main() { n = readint() ; m = readint() ; int a , b , c , d ; int Max = 0 ; for(int i = 0 ; i < m ; ++i) { a = readint() ; b = readint() ; c = readint() ; d = readint() ; Max = max(Max , c) ; adj[a].push_back(edge(b , c , d)) ; adj[b].push_back(edge(a , c , d)) ; } long long cons = 1e17 ; for(int i = 1 ; i <= n ; ++i) { for(int j = 0 ; j < MAXT ; ++j) dp[i][j] = cons , vis[i][j] = cons; } //dijkstra priority_queue< pair<int , pair<int , int> > , vector< pair<int , pair<int , int> > > , greater< pair<int , pair<int , int> > > >q ; q.push({0 , {0 , 1}}) ; dp[1][0] = 0 ; bool flag = 0 ; while(!q.empty()) { pair<int , pair<int , int> >p = q.top() ; q.pop() ; int node = p.second.second , sumc = p.first , sumt = p.second.first ; if(dp[node][sumt] < sumc) continue ; for(auto &child : adj[node]) { int nto = child.to ; int ntime = child.time + sumt; int ncost = child.cost + sumc; if(ntime >= MAXT) continue ; if(dp[nto][ntime] > ncost) { dp[nto][ntime] = ncost ; q.push({ncost , {ntime , nto}}) ; } } } for(int i = 2 ; i <= n ; ++i) { ans[i] = cons ; for(int j = 1 ; j < MAXT ; ++j) { if(dp[i][j] == cons) continue ; ans[i] = min(ans[i] , (j * 1ll) * (dp[i][j] * 1ll)) ; } } for(int i = 2 ; i <= n ; ++i) { if(ans[i] == cons) ans[i] = -1 ; printf("%lld\n" , ans[i]); } return 0 ; }

Compilation message (stderr)

ceste.cpp: In function 'int main()':
ceste.cpp:75:10: warning: unused variable 'flag' [-Wunused-variable]
     bool flag = 0 ;
          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...