oj.uz

Submission #896448

# Submission time Handle Problem Language Result Execution time Memory
896448 2024-01-01T13:18:02 Z Unforgettablepl Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 10636 KB 
//#pragma GCC optimize "Ofast"
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<ll> point;
#define X real()
#define Y imag()
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const ll INF = 1e17;
const ll sqrtn = 440;
const ll modulo = 1e9+7;
const ll siz = 262144;
const ll hashp = 923981238;
const ll hashm = 932439994;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define int ll

int reversededge;

struct edge{
    int u,v,c,d,idx;
    bool Reverse;
    edge(){}
    edge(int u,int v,int c,int d,int idx,bool R=false):u(u),v(v),c(c),d(d),idx(idx),Reverse(R){}
    bool isActive(){
        if(Reverse)return reversededge==idx;
        else return reversededge!=idx;
    }
};

edge edgelist[50001];
vector<edge> adj[201];
int distfrom1[201];
int distfromn[201];
int distto1[201];
int distton[201];
bool visited[201];
int n;

int dijkastra(){
    int cost = INF;
    int cost2 = INF;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
    q.emplace(0,1);
    while(!q.empty()){
        auto curr = q.top();q.pop();
        if(visited[curr.second])continue;
        if(curr.second==n){cost=curr.first;break;}
        visited[curr.second]=true;
        for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
    }
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)visited[i]=false;
    q.emplace(0,n);
    while(!q.empty()){
        auto curr = q.top();q.pop();
        if(visited[curr.second])continue;
        if(curr.second==1) {cost2 = curr.first;break;}
        visited[curr.second]=true;
        for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
    }
    for(int i=1;i<=n;i++)visited[i]=false;
    if(cost==INF or cost2==INF)return INF;
    else return cost+cost2;
}


void solve() {
    int m;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,c,d;
        cin >> u >> v >> c >> d;
        edgelist[i] = {u,v,c,d,i};
        adj[u].emplace_back(u,v,c,d,i);
        adj[v].emplace_back(v,u,c,d,i,true);
    }
    int ans = dijkastra();
    for(int i=1;i<=m;i++){
        reversededge=i;
        int inter = dijkastra();
        ans = min(ans,edgelist[i].d+inter);
    }
    cout << (ans==INF ? -1 : ans) << '\n';
//    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
//    q.emplace(0,1);
//    while(!q.empty()){
//        auto curr = q.top();q.pop();
//        if(visited[curr.second])continue;
//        visited[curr.second]=true;
//        distfrom1[curr.second]=curr.first;
//        for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
//    }
//    for(int i=1;i<=n;i++)visited[i]=false;
//    q.emplace(0,n);
//    while(!q.empty()){
//        auto curr = q.top();q.pop();
//        if(visited[curr.second])continue;
//        visited[curr.second]=true;
//        distfromn[curr.second]=curr.first;
//        for(auto&i:adj[curr.second])if(i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
//    }
//    for(int i=1;i<=n;i++)visited[i]=false;
//    q.emplace(0,1);
//    while(!q.empty()){
//        auto curr = q.top();q.pop();
//        if(visited[curr.second])continue;
//        visited[curr.second]=true;
//        distto1[curr.second]=curr.first;
//        for(auto&i:adj[curr.second])if(!i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
//    }
//    for(int i=1;i<=n;i++)visited[i]=false;
//    q.emplace(0,n);
//    while(!q.empty()){
//        auto curr = q.top();q.pop();
//        if(visited[curr.second])continue;
//        visited[curr.second]=true;
//        distton[curr.second]=curr.first;
//        for(auto&i:adj[curr.second])if(!i.isActive() and !visited[i.v])q.emplace(curr.first+i.c,i.v);
//    }
//    for(int i=1;i<=n;i++)visited[i]=false;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("cses.fi.txt","r",stdin);
//    freopen(".out","w",stdout);
//    int t;
//    cin >> t;
//    while(t--)
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 604 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 35 ms 604 KB Output is correct
4 Correct 48 ms 604 KB Output is correct
5 Correct 48 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 476 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 64 ms 488 KB Output is correct
10 Correct 87 ms 688 KB Output is correct
11 Correct 79 ms 688 KB Output is correct
12 Correct 85 ms 600 KB Output is correct
13 Correct 34 ms 604 KB Output is correct
14 Correct 41 ms 600 KB Output is correct
15 Correct 26 ms 600 KB Output is correct
16 Correct 54 ms 600 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 10636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 1074 ms 8012 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 604 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 35 ms 604 KB Output is correct
4 Correct 48 ms 604 KB Output is correct
5 Correct 48 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 476 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 64 ms 488 KB Output is correct
10 Correct 87 ms 688 KB Output is correct
11 Correct 79 ms 688 KB Output is correct
12 Correct 85 ms 600 KB Output is correct
13 Correct 34 ms 604 KB Output is correct
14 Correct 41 ms 600 KB Output is correct
15 Correct 26 ms 600 KB Output is correct
16 Correct 54 ms 600 KB Output is correct
17 Execution timed out 1055 ms 10636 KB Time limit exceeded
18 Halted 0 ms 0 KB -