제출 #824327

#제출 시각아이디문제언어결과실행 시간메모리
824327trangtranha28Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
282 ms41044 KiB
#include <bits/stdc++.h> #include <iostream> #include <algorithm> #include <stdio.h> #include <climits> #include <vector> #include <queue> #include <map> #include <set> #define int long long using namespace std; const int MAXN = 1e5 + 2; int n, m; int s, t, src, tar; int dis[MAXN] = {0}, dis2[4][MAXN] = {0}; bool vis[MAXN] = {false}; vector <pair <int, int> > adj[MAXN]; vector <int> pp[MAXN], adj2[MAXN], radj[MAXN]; void Dijkstra() { // reset: memset(dis, 0x3f3f3f3f, sizeof(dis)); memset(dis2, 0x3f3f3f3f, sizeof(dis2)); // reset: dis[s] = 0; // main: priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq; pq.push(make_pair(dis[s], s)); while(pq.empty() == false) { pair <int, int> p = pq.top(); pq.pop(); int d = p.first; int v = p.second; if(d != dis[v]) { continue; } for(int i = 0; i < (int)(adj[v].size()); i++) { int u = adj[v][i].first; int w = adj[v][i].second; if(dis[u] > dis[v] + w) { dis[u] = dis[v] + w; pq.push(make_pair(dis[u], u)); pp[u] = {v}; } else if(dis[u] == dis[v] + w) { pp[u].push_back(v); } } } return; } void Dijkstra2() { // reset: dis2[0][src] = 0; // main: priority_queue <pair <int, pair <int, int> >, vector <pair <int, pair <int, int> > >, greater <pair <int, pair <int, int> > > > pq2; pq2.push(make_pair(dis2[0][src], make_pair(0, src))); while(pq2.empty() == false) { pair <int, pair <int, int> > p2 = pq2.top(); pq2.pop(); int d = p2.first; int i = p2.second.first; int v = p2.second.second; // output: if(v == tar) { cout << d << "\n"; return; } if(d != dis2[i][v]) { continue; } for(int j = 0; j < (int)(adj[v].size()); j++) { int u = adj[v][j].first; int w = adj[v][j].second; int ni = 0; if(i != 0) { ni = 3; } if(dis2[ni][u] > dis2[i][v] + w) { dis2[ni][u] = dis2[i][v] + w; pq2.push(make_pair(dis2[ni][u], make_pair(ni, u))); } } if(i == 0 || i == 1) { for(int j = 0; j < (int)(adj2[v].size()); j++) { int u = adj2[v][j]; if(dis2[1][u] > dis2[i][v]) { dis2[1][u] = dis2[i][v]; pq2.push(make_pair(dis2[1][u], make_pair(1, u))); } } } if(i == 0 || i == 2) { for(int j = 0; j < (int)(radj[v].size()); j++) { int u = radj[v][j]; if(dis2[2][u] > dis2[i][v]) { dis2[2][u] = dis2[i][v]; pq2.push(make_pair(dis2[2][u], make_pair(2, u))); } } } } return; } void programme() { // input: cin >> n >> m >> s >> t >> src >> tar; for(int i = 1; i <= m; i++) { int a, b, w; cin >> a >> b >> w; adj[a].push_back(make_pair(b, w)); adj[b].push_back(make_pair(a, w)); } // solve: Dijkstra(); queue <int> q; q.push(t); vis[t] = true; while(q.empty() == false) { int v = q.front(); q.pop(); for(int i = 0; i < (int)(pp[v].size()); i++) { int u = pp[v][i]; adj2[v].push_back(u); radj[u].push_back(v); if(vis[u] == false) { vis[u] = true; q.push(u); } } } // output: Dijkstra2(); return; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("_mint.inp", "r", stdin); // freopen("_mint.out", "w", stdout); programme(); return 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...