제출 #964121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964121		Akshat369	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1052 ms	4448 KiB

ho_t4

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define INF (int)1e18
#define endl '\n'
const int mod = 1000 * 1000 * 1000 + 7;
const int N = 100005;
#define f first
#define s second
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define rrep(i, a, b) for(int i = (a); i > (b); i--)
#define vi vector<int>
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
  
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
/*
 
*/
 
struct node{
    int u , v , c , d;
};
 
vector<int> dij(int src, vector<pii> adj[], int n) {
    vector<int> dis(n, INF);
    vector<int> vis(n, false);
 
    dis[src] = 0;
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({0, src});
 
    while (!pq.empty()) {
        auto uu = pq.top();
        pq.pop();
        int u = uu.second;
        if (vis[u]) continue;
        vis[u] = true;
 
        for (auto& vv : adj[u]) {
            int v = vv.first;
            int weight = vv.second;
            if (dis[v] > dis[u] + weight) {
                dis[v] = dis[u] + weight;
                pq.push({dis[v], v});
            }
        }
    }
    return dis;
}
 
 
void Solve() {
    int n , m; cin>>n>>m;
    vector<node> edge(m);
    for (int i = 0; i < m ; ++i) {
        cin>>edge[i].u>>edge[i].v>>edge[i].c>>edge[i].d;
    }
    int ans = 1e18;
    for(int i = 0 ; i < m ; i++){
        vector<pii> adj[n+1];
        for(int j = 0 ; j < m ; j++){
            if (i==j){
                adj[edge[j].v].push_back({edge[j].u,edge[j].c+edge[j].d});
            }
            else  adj[edge[j].u].push_back({edge[j].v,edge[j].c});
        }
        vi dis1(n+1), dis2(n+1) ;
        dis1 = dij(1, adj, n+1);
        dis2 = dij(n, adj, n+1);
//        debug(i,dis1);
//        debug(i,dis2);
//        for (int j = 0; j < n + 1; ++j) {
//            debug(j,adj[j]);
//        }
        ans = min(ans, dis1[n] + dis2[1]);
    }
  	if(ans>=(int)1e18){
      cout<<-1<<endl;
    }
 	else cout << ans << endl;
}
 
int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    int t = 1;
 //   cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63