Submission #1041401

#TimeUsernameProblemLanguageResultExecution timeMemory
1041401khanhtbRobot (JOI21_ho_t4)C++14
0 / 100
143 ms27328 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld long double #define pb push_back #define pf push_front #define vi vector<ll> #define vii vector<vi> #define pll pair<ll, ll> #define vpll vector<pll> #define all(a) a.begin(), a.end() #define fi first #define se second using namespace std; const ll mod = 1e9+7; const ll inf = 1e18; const ll blocksz = 320; const ll N = 3e5+8; ll d[N]; struct edge{ ll v,c,w; }; int n,m; vector<edge> g[N]; ll dijkstra(){ fill(d+1,d+n+1,inf); priority_queue<pll,vpll,greater<pll>> pq; pq.push({0,1}); d[1] = 0; while(pq.size()){ int u = pq.top().se, dist = pq.top().fi; pq.pop(); if(dist > d[u]) continue; if(u == n) return dist; map<int,int> cnt; for(edge ed:g[u]){ int v = ed.v, c = ed.c; ll w = ed.w; cnt[c] += w; } for(edge ed:g[u]){ int v = ed.v, c = ed.c; ll w = ed.w; if(cnt[c] == w){ if(d[v] > d[u]){ d[v] = d[u]; pq.push({d[v],v}); } } else{ ll cost = min(w,cnt[c]-w); if(d[v] > d[u]+cost){ d[v] = d[u]+cost; pq.push({d[v],v}); } } } } return -1; } void solve(){ cin >> n >> m; for(int i = 1; i <= m; i++){ int u,v,c; ll w; cin >> u >> v >> c >> w; g[u].pb({v,c,w}); g[v].pb({u,c,w}); } cout << dijkstra(); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll T = 1; // cin >> T; for (ll i = 1; i <= T; i++) { solve(); cout << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'long long int dijkstra()':
Main.cpp:38:17: warning: unused variable 'v' [-Wunused-variable]
   38 |             int v = ed.v, c = ed.c;
      |                 ^
Main.cpp: In function 'int main()':
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...