Submission #1162871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162871		irmuun	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1095 ms	3144 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pll pair<ll,ll>

const ll N=2e2,M=5e4;

ll n,m;
ll dist[N];
vector<ll>g[N];

struct Edge{
	ll a,b,c,d;
	Edge():a(-1),b(-1),c(-1),d(-1){}
};

Edge edge[M];

ll dijkstra(ll s,ll t){
	fill(dist,dist+N,(ll)1e18);
	dist[s]=0;
	priority_queue<pll,vector<pll>,greater<pll>>pq;
	pq.push({0,s});
	while(!pq.empty()){
		auto [D,x]=pq.top();
		pq.pop();
		if(dist[x]!=D) continue;
		if(x==t) return dist[x];
		for(ll i:g[x]){
			if(edge[i].a==x){
				if(dist[x]+edge[i].c<dist[edge[i].b]){
					dist[edge[i].b]=dist[x]+edge[i].c;
					pq.push({dist[edge[i].b],edge[i].b});
				}
			}
		}
	}
	return (ll)1e18;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>edge[i].a>>edge[i].b>>edge[i].c>>edge[i].d;
		edge[i].a--;
		edge[i].b--;
		g[edge[i].a].pb(i);
		g[edge[i].b].pb(i);
	}
	ll ans=(ll)1e18;
	for(ll i=0;i<=m;i++){
		if(i<m){
			swap(edge[i].a,edge[i].b);
			ans=min(ans,dijkstra(0,n-1)+dijkstra(n-1,0)+edge[i].d);
			swap(edge[i].a,edge[i].b);
		}
		else{
			ans=min(ans,dijkstra(0,n-1)+dijkstra(n-1,0));
		}
	}
	if(ans==(ll)1e18) ans=-1;
	cout<<ans;
}

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