제출 #1026537

#제출 시각아이디문제언어결과실행 시간메모리
1026537dwuyRobot (JOI21_ho_t4)C++14
34 / 100
3077 ms71332 KiB
/// - dwuy - #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) (int)((s).size()) #define MASK(k)(1LL<<(k)) #define TASK "test" #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 200005; struct Edge{ int u, v, c, col; Edge(int u=0, int v=0, int col=0, int c=0){ this->u = u; this->v = v; this->col = col; this->c = c; } int other(int x){ return u ^ v ^ x; } }; int n, m; Edge edges[MX]; vector<int> G[MX]; void nhap(){ cin >> n >> m; for(int i=1; i<=m; i++){ int u, v, col, c; cin >> u >> v >> col >> c; edges[i] = Edge(u, v, col, c); G[u].push_back(i); G[v].push_back(i); } } int d[MX]; map<int, int> sum[MX]; map<int, int> f[MX]; void solve(){ for(int i=1; i<=m; i++){ int u = edges[i].u; int v = edges[i].v; int c = edges[i].c; int col = edges[i].col; sum[u][col] += c; sum[v][col] += c; } priority_queue<tpiii, vector<tpiii>, greater<tpiii>> Q; memset(d, 0x3f, sizeof d); d[1] = 0; Q.push({0, -1, 1}); while(Q.size()){ int du, cl, u; tie(du, cl, u) = Q.top(); Q.pop(); if(cl == -1 && d[u] != du) continue; if(cl != -1 && f[u][cl] != du) continue; if(cl == -1){ for(int i: G[u]){ int c = edges[i].c; int cl = edges[i].col; int v = edges[i].other(u); int scl = sum[u][cl]; if(f[v].find(cl) == f[v].end()) f[v][cl] = 1e18; if(d[v] > du + scl - c){ d[v] = du + scl - c; Q.push({d[v], -1, v}); } if(d[v] > du + c){ d[v] = du + c; Q.push({d[v], -1, v}); } if(f[v][cl] > du){ f[v][cl] = du; Q.push({f[v][cl], cl, v}); } } } else{ for(int i: G[u]) if(edges[i].col == cl){ int nc = edges[i].c; int v = edges[i].other(u); if(f[v].find(cl) == f[v].end()) f[v][cl] = 1e18; int scl = sum[u][cl]; if(d[v] > du + scl - nc){ d[v] = du + scl - nc; Q.push({d[v], -1, v}); } } } } cout << (d[n] == d[0]? -1 : d[n]); } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...