| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833522 |
2023-08-22T06:27:31 Z |
vjudge1 |
Exam (eJOI20_exam) |
C++17 |
|
1000 ms |
269488 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];
ll cost;
ll n, m, s, t, u, v, mindist = INF, mindist2 = INF, mindisttotal = INF;
ll input1, input2, input3;
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);
}
last[cur].clear();
}
void dfs(ll node, ll c){
if(c == cost && node == t){
djikstra2(v);
mindist = INF;
mindist2 = INF;
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(mindisttotal, min(mindist+mindist2, dist2[u]));
return;
}
for(auto e : adj[node]){
if(vis[e.second]) continue;
vis[e.second] = true;
special.push_back(e.second);
dfs(e.second, c+e.first);
vis[e.second] = false;
special.pop_back();
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
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(n <= 300){
for(int i = 0; i < N; i++){
last[i].clear();
}
djikstra1(s);
cost = dist1[t];
vis[s] = true;
special.push_back(s);
special.push_back(t);
dfs(s, 0);
cout << mindisttotal << endl;
return 0;
}
if(s == u){
djikstra1(s);
finds(t, s);
ada[s] = true;
ada[t] = true;
// sort(special.begin(), special.end());
// special.erase(unique(special.begin(), special.end()), special.end());
djikstra2(v);
for(int x = 1; x <= n; x++){
if(ada[x]) 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);
ada[s] = true;
ada[t] = true;
// sort(special.begin(), special.end());
// special.erase(unique(special.begin(), special.end()), special.end());
djikstra2(v);
for(int x = 1; x <= n; x++){
if(ada[x]) mindist = min(mindist, dist2[x]);
// cout << x << " " << dist2[x] << endl;
}
djikstra3(u);
for(int x = 1; x <= n; x++){
if(ada[x]) 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 |
Execution timed out |
1066 ms |
269488 KB |
Time limit exceeded |
| 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 |
7 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 |
Execution timed out |
1066 ms |
269488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
269488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
