Submission #222588

#	Time	Username	Problem	Language	Result	Execution time	Memory
222588		astoria	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	419 ms	4856 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define MAXN 205
#define MAXM 50005
int n,m;
int dist[MAXN][MAXN];
array<int,4> edg[MAXM];
vector<pair<int,int> > adj[MAXN];

int EDGST;

int dijkstra(int st, int rev){
	int dis[MAXN];
	for(int i=0; i<MAXN; i++) dis[i] = 1e17;
	dis[st] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;//w,nd
	pq.push({0,st});
	while(!pq.empty()){
		int wei = pq.top().first, v=pq.top().second; pq.pop();
		if(dis[v] != wei) continue;
		for(auto ahc : adj[v]){
			if(ahc.second==rev) continue;
			int nd = ahc.first; int nw = edg[ahc.second][2];
			if(wei + nw < dis[nd]){
				dis[nd] = wei+nw;
				pq.push({dis[nd],nd});
			}
		}
		if(v==EDGST){
			int nd = edg[rev][0]; int nw = edg[rev][2];
			if(wei + nw < dis[nd]){
				dis[nd] = wei+nw;
				pq.push({dis[nd],nd});
			}
		}
	}
	if(st==n) return dis[1];
	else return dis[n];
}

int32_t main(){
	for(int i=0; i<MAXN; i++){
		for(int j=0; j<MAXN; j++){
			if(i==j) dist[i][j]=0;
			else dist[i][j]=1e17;
		}
	}
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u,v,c,d;
		cin>>u>>v>>c>>d;
		edg[i] = {u,v,c,d};
		adj[u].push_back(make_pair(v,i));
		dist[u][v]=min(dist[u][v],c);
	}
	
	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
			}
		}
	}
	
	int an = dist[1][n] + dist[n][1];
	for(int i=0; i<m; i++){
		//can lower?
		int dis_to = min(dist[1][n], dist[1][edg[i][1]] + edg[i][2] + dist[edg[i][0]][n]);
		int dis_fr = min(dist[n][1], dist[n][edg[i][1]] + edg[i][2] + dist[edg[i][0]][1]);
		if(dis_to + dis_fr + edg[i][3] < an){
			EDGST = edg[i][1];
			int dis1 = dijkstra(1,i);
			int dis2 = dijkstra(n,i);
			//if(i==1) cout<<dis1<<' '<<dis2<<endl;
			an = min(an, dis1+dis2+edg[i][3]);
		}
	}
	if(an < 1e15) cout<<an;
	else cout<<-1;
}

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