Submission #217114

#	Time	Username	Problem	Language	Result	Execution time	Memory
217114		jamielim	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	1095 ms	2552 KiB

ho_t4

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

int n,m;
vector<pair<pair<int,int>,int> > adj[205];
const long long INF=1000000000000000010LL;
int d[50005];
bool use[50005];

long long f(){
	/*for(int j=0;j<n;j++){
		for(int k=0;k<(int)adj[j].size();k++){
			if(use[adj[j][k].second])printf("%d %d\n",j,adj[j][k].first.first);
		}
	}
	printf(".\n");*/
	priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > pq;
	pq.push(make_pair(0,0));
	long long dist1[205];
	for(int i=0;i<n;i++)dist1[i]=INF;
	dist1[0]=0;
	while(!pq.empty()){
		int cur=pq.top().second;pq.pop();
		for(int i=0;i<(int)adj[cur].size();i++){
			if(use[adj[cur][i].second]){
				int a=adj[cur][i].first.first,b=adj[cur][i].first.second;
				if(dist1[a]>dist1[cur]+b){
					dist1[a]=dist1[cur]+b;
					pq.push(make_pair(dist1[a],a));
				}
			}
		}
	}
	pq.push(make_pair(0,n-1));
	long long dist2[205];
	for(int i=0;i<n;i++)dist2[i]=INF;
	dist2[n-1]=0;
	while(!pq.empty()){
		int cur=pq.top().second;pq.pop();
		for(int i=0;i<(int)adj[cur].size();i++){
			if(use[adj[cur][i].second]){
				int a=adj[cur][i].first.first,b=adj[cur][i].first.second;
				if(dist2[a]>dist2[cur]+b){
					dist2[a]=dist2[cur]+b;
					pq.push(make_pair(dist2[a],a));
				}
			}
		}
	}
	return min(INF,dist1[n-1]+dist2[0]);
}

int main(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=0;i<m;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d[i]);a--;b--;
		adj[a].push_back(make_pair(make_pair(b,c),i));
	}
	for(int i=0;i<=m;i++)use[i]=1;
	long long ans=f();
	for(int i=0;i<n;i++){
		for(int j=0;j<(int)adj[i].size();j++){
			use[adj[i][j].second]=0;
			pair<pair<int,int>,int > x=adj[i][j];
			x.first.first=i;x.second=m;
			adj[adj[i][j].first.first].push_back(x);
			ans=min(ans,f()+d[adj[i][j].second]);
			use[adj[i][j].second]=1;
			adj[adj[i][j].first.first].pop_back();
		}
	}
	if(ans>=INF)printf("-1");
	else printf("%lld",ans);
}

Compilation message (stderr)

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

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