Submission #733508

#	Time	Username	Problem	Language	Result	Execution time	Memory
733508		pcc	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1094 ms	3972 KiB

ho_t4

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

#pragma GCC optimize("O3")
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 202;
const int mxn2 = 5e4+10;
const ll inf = 1e18;
ll dist[mxn];

struct edge{
	ll from,to,val,id,cost;
	edge(){}
	edge(ll ff,ll tt,ll vv,ll cc,ll ii){
		from = ff,to = tt,val = vv,cost = cc;
		id = ii;
	}
};

vector<edge> paths[mxn];
edge edges[mxn2];
int n,m;

ll dijkstra(int s,int no){
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	fill(dist,dist+mxn,inf);
	dist[s] = 0;
	pq.push({0,s});
	while(!pq.empty()){
		auto now = pq.top();
		pq.pop();
		if(now.fs != dist[now.sc])continue;
		for(auto &nxt:paths[now.sc]){
			if(nxt.id == no)continue;
			if(nxt.val+dist[now.sc]<dist[nxt.to]){
				dist[nxt.to] = nxt.val+dist[now.sc];
				pq.push({dist[nxt.to],nxt.to});
			}
		}
	}
	if(s == 1)return dist[n];
	else return dist[1];
}

void solve(){
	cin>>n>>m;
	ll ans = inf;
	if(m>1000){
		for(int i = 2;i<=m;i+=2){
			ll c;
			edges[i].id = i>>1;
			cin>>edges[i].from>>edges[i].to>>edges[i].val>>edges[i].cost;
			cin>>c>>c>>c>>c;
			edges[i].cost = min(edges[i].cost,c);
			paths[edges[i].from].push_back(edges[i]);
		}
	}
	else{
		for(int i = 1;i<=m;i++){
			ll c;
			edges[i].id = i>>1;
			cin>>edges[i].from>>edges[i].to>>edges[i].val>>edges[i].cost;
			paths[edges[i].from].push_back(edges[i]);
		}
	}
	ans = dijkstra(1,0)+dijkstra(n,0);
	for(int i = 1;i<=m;i++){
		paths[edges[i].to].push_back(edge(edges[i].to,edges[i].from,edges[i].val,edges[i].cost,-edges[i].id));
		ll tmp = edges[i].cost+dijkstra(1,i)+dijkstra(n,i);
		ans = min(ans,tmp);
		paths[edges[i].to].pop_back();
	}
	cout<<(ans>=inf?-1:ans)<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	while(t--)solve();
}

Compilation message (stderr)

ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:64:7: warning: unused variable 'c' [-Wunused-variable]
   64 |    ll c;
      |       ^

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