Submission #237268

#	Time	Username	Problem	Language	Result	Execution time	Memory
237268		AMO5	Olympic Bus (JOI20_ho_t4)	C++98	5 / 100	1084 ms	3828 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;
const int mxn=202;
ll dist1[mxn],dist2[mxn],d[50005];
vector<pair<int,ll>>adj[mxn];
int n;

struct flag{
	int u,v; ll c;
	flag(int u, int v, ll c):u(u),v(v),c(c){}
};

vector<flag>str;
//subtask 1
ll dij(int ind){ 
	//set all dist = INF
	for(int i=0; i<n; i++)
		dist1[i]=dist2[i]=ll(1e18);
	
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
	//from 1 to n;
	dist1[0]=0LL;
	pq.push({dist1[0],0});
	while(!pq.empty()){
		auto tp = pq.top();
		pq.pop();
		int u = tp.se;
		if(u==n-1)break;
		if(u==str[ind].v){
			int v = str[ind].u;
			ll w = str[ind].c;
			if(dist1[v]>dist1[u]+w){
				dist1[v] = dist1[u]+w;
				pq.push({dist1[v],v});
			}
		}
		for(auto x:adj[u]){
			int v = x.fi;
			ll w = x.se;
			if(str[ind].u==u&&str[ind].v==v&&str[ind].c==w)continue;
			if(dist1[v]>dist1[u]+w){
				dist1[v] = dist1[u]+w;
				pq.push({dist1[v],v});
			}
		}
	}
	//from n to 1;
	dist2[n-1]=0LL;
	pq.push({dist2[n-1],n-1});
	while(!pq.empty()){
		auto tp = pq.top();
		pq.pop();
		int u = tp.se;
		if(u==0)break;
		if(u==str[ind].v){
			int v = str[ind].u;
			ll w = str[ind].c;
			if(dist2[v]>dist2[u]+w){
				dist2[v] = dist2[u]+w;
				pq.push({dist2[v],v});
			}
		}
		for(auto x:adj[u]){
			int v = x.fi;
			ll w = x.se;
			if(str[ind].u==u&&str[ind].v==v&&str[ind].c==w)continue;
			if(dist2[v]>dist2[u]+w){
				dist2[v] = dist2[u]+w;
				pq.push({dist2[v],v});
			}
		}
	}
	if(dist1[n-1]==1e18||dist2[0]==1e18)return 2e18;
	return dist1[n-1]+dist2[0];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int m; 
	cin >> n >> m;
	str.eb(-1,-1,0);
	d[0]=0LL;
	for(int i=1; i<=m; i++){
		int u,v; ll c;
		cin >> u >> v >> c >> d[i];
		u--; v--;
		adj[u].eb(v,c);
		str.eb(u,v,c);
	}
	ll ans = (ll)2e18;
	for(int i=0; i<=m; i++){
		ll now = dij(i);
		ans = min(ans, now+d[i]);
	}
	if(ans==2e18)ans = -1;
	cout << ans << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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