oj.uz

Submission #237263

# Submission time Handle Problem Language Result Execution time Memory
237263 2020-06-05T14:52:28 Z AMO5 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 6 ms 768 KB 
#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[mxn];
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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -