제출 #1091944

#제출 시각아이디문제언어결과실행 시간메모리
1091944coldbr3wRobot (JOI21_ho_t4)C++17
34 / 100
3075 ms82248 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 2e5 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 350; ll n,m; struct ccjv{ll v,c,p;}; struct ngu{ll u,c,col;}; map<ll,ll>d[N]; struct cmp{ bool operator()(const ngu &a, const ngu &b){ return a.c > b.c; } }; vector<ccjv>adj[N]; map<ll,ll>mp[N]; void to_thic_cau(){ cin >> n >> m; for(int i = 1; i <= m;i++){ ll u,v,c,p; cin >> u >> v >> c >> p; mp[u][c] += p; mp[v][c] += p; adj[u].pb({v,c,p}); adj[v].pb({u,c,p}); } for(int i = 1; i <= n;i++){ for(auto j : adj[i]) d[i][j.c] = inf; d[i][0] = inf; } d[1][0] = 0; priority_queue<ngu, vector<ngu>, cmp>q; q.push({1, d[1][0], 0}); while(q.size()){ ll u = q.top().u, cost = q.top().c, col = q.top().col; q.pop(); if(cost != d[u][col]) continue; for(auto x : adj[u]){ ll v = x.v, c = x.c, p = x.p; if(col == 0){ // di nhu bthg if(d[v][0] > d[u][0] + min(p, mp[u][c] - p)){ d[v][0] = d[u][0] + min(p, mp[u][c] - p); q.push({v, d[v][0], 0}); } // thay mau canh if(d[v][c] > d[u][0]){ d[v][c] = d[u][0]; q.push({v, d[v][c], c}); } } else{ // dung lai mau nhu bthg if(c == col){ if(d[u][col] + mp[u][col] - p < d[v][0]){ d[v][0] = d[u][col] + mp[u][col] - p; q.push({v, d[v][0], 0}); } } } } } cout << (d[n][0] == inf ? -1 : d[n][0]) << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...