Submission #565315

#	Time	Username	Problem	Language	Result	Execution time	Memory
565315		MilosMilutinovic	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	1083 ms	3532 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=205;
const int M=500050;
const ll inf=1e18;
int n,m;
struct edge{int u,v,c,d;};
vector<edge> E[N];
edge edges[M];
ll dist[2][N];
void Dijkstra(int st,ll* dist){
	for(int i=1;i<=n;i++)dist[i]=inf;
	dist[st]=0;
	priority_queue<pair<ll,int>> pq;
	pq.push({0,st});
	while(!pq.empty()){
		ll d=-pq.top().second;
		int u=pq.top().second;
		pq.pop();
		if(dist[u]<d)continue;
		for(auto e:E[u]){
			int v=e.v;
			int c=e.c;
			if(dist[v]>dist[u]+c){
				dist[v]=dist[u]+c;
				pq.push({-dist[v],v});
			}
		}
	}
}
ll Solve(int idx){
	for(int i=1;i<=n;i++)E[i].clear();
	swap(edges[idx].u,edges[idx].v);
	for(int i=1;i<=m;i++)E[edges[i].u].push_back(edges[i]);
	Dijkstra(1,dist[0]);
	Dijkstra(n,dist[1]);
	swap(edges[idx].u,edges[idx].v);
	return dist[0][n]+dist[1][1]+edges[idx].d;
}
int main(){
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%i %i %i %i",&edges[i].u,&edges[i].v,&edges[i].c,&edges[i].d);
		E[edges[i].u].push_back(edges[i]);
	}
	Dijkstra(1,dist[0]);
	Dijkstra(n,dist[1]);
	ll ans=dist[0][n]+dist[1][1];
	for(int i=1;i<=m;i++)ans=min(ans,Solve(i));
	if(ans>=inf)ans=-1;
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
ho_t4.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%i %i %i %i",&edges[i].u,&edges[i].v,&edges[i].c,&edges[i].d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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