| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833346 |
2023-08-22T04:46:57 Z |
vjudge1 |
Exam (eJOI20_exam) |
C++17 |
|
8 ms |
9988 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100005;
const ll INF = 1e15;
vector<pair<ll,ll>> adj[N];
// vector<pair<ll,ll>> adj2[N];
vector<ll> last[N];
ll dist1[N], dist2[N], dist3[N];
vector<ll> special;
bool ada[N], vis[N];
void djikstra1(ll start){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
ll cur_node, cur_dist, next_dist, next_node;
for(int i = 0; i < N; i++){
dist1[i] = INF;
}
dist1[start] = 0;
pq.push({0,start});
while(!pq.empty()){
cur_node = pq.top().second;
cur_dist = pq.top().first;
pq.pop();
for(auto e : adj[cur_node]){
next_dist = cur_dist + e.first;
next_node = e.second;
if(dist1[next_node] < next_dist) continue;
else if(dist1[next_node] == next_dist){
last[next_node].push_back(cur_node);
}
else{
last[next_node].clear();
last[next_node].push_back(cur_node);
dist1[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
}
}
void djikstra2(ll start){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
ll cur_node, cur_dist, next_dist, next_node;
for(int i = 0; i < N; i++){
dist2[i] = INF;
}
dist2[start] = 0;
pq.push({0,start});
while(!pq.empty()){
cur_node = pq.top().second;
cur_dist = pq.top().first;
pq.pop();
for(auto e : adj[cur_node]){
next_dist = cur_dist + e.first;
next_node = e.second;
if(dist2[next_node] < next_dist) continue;
// else if(dist2[next_node] == next_dist){
// last[next_node].push_back(cur_node);
// }
else{
// last[next_node].clear();
// last[next_node].push_back(cur_node);
dist2[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
}
}
void djikstra3(ll start){
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
ll cur_node, cur_dist, next_dist, next_node;
for(int i = 0; i < N; i++){
dist3[i] = INF;
}
dist3[start] = 0;
pq.push({0,start});
while(!pq.empty()){
cur_node = pq.top().second;
cur_dist = pq.top().first;
pq.pop();
for(auto e : adj[cur_node]){
next_dist = cur_dist + e.first;
next_node = e.second;
if(dist3[next_node] < next_dist) continue;
// else if(dist2[next_node] == next_dist){
// last[next_node].push_back(cur_node);
// }
else{
// last[next_node].clear();
// last[next_node].push_back(cur_node);
dist3[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
}
}
void finds(ll cur, ll finish){
if(cur == finish){
if(!ada[cur]){
special.push_back(cur);
ada[cur] = true;
}
return;
}
for(auto x : last[cur]){
if(vis[x]) continue;
vis[x] = true;
if(!ada[x]){
special.push_back(x);
ada[x] = true;
}
finds(x, finish);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, s, t, u, v, mindist = INF, mindist2 = INF, mindisttotal = INF;
ll input1, input2, input3;
cin >> n >> m >> s >> t >> u >> v;
for(int i = 0; i < m; i++){
cin >> input1 >> input2 >> input3;
adj[input1].push_back({input3, input2});
adj[input2].push_back({input3, input1});
// adj2[input2].push_back({input3, input1});
}
for(int i = 0 ; i< N; i++){
ada[i] = false;
vis[i] = false;
}
if(s == u){
djikstra1(s);
finds(t, s);
special.push_back(s);
special.push_back(t);
// sort(special.begin(), special.end());
// special.erase(unique(special.begin(), special.end()), special.end());
djikstra2(v);
for(auto x : special){
mindist = min(mindist, dist2[x]);
// cout << x << " " << dist2[x] << endl;
}
mindist = min(mindist, dist2[u]);
// for(int i = 1; i <= n; i++){
// for(auto x : last[i]){
// cout << i << ":" << x << " ";
// }
// cout << endl;
// }
cout << mindist;
return 0;
}
else{
djikstra1(s);
finds(t, s);
special.push_back(s);
special.push_back(t);
// sort(special.begin(), special.end());
// special.erase(unique(special.begin(), special.end()), special.end());
djikstra2(v);
for(auto x : special){
mindist = min(mindist, dist2[x]);
// cout << x << " " << dist2[x] << endl;
}
djikstra3(u);
for(auto x : special){
mindist2 = min(mindist2, dist3[x]);
// cout << x << " " << dist2[x] << endl;
}
mindisttotal = min(mindist+mindist2, dist3[v]);
cout << mindisttotal;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
9940 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
9940 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9988 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
