Submission #205359

#	Time	Username	Problem	Language	Result	Execution time	Memory
205359		TadijaSebez	Olympic Bus (JOI20_ho_t4)	C++11	37 / 100	1098 ms	4856 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=205;
const int M=50050;
const int inf=2e9+7;
struct Edge{int u,v,c,d;};
Edge edges[M];
bool bridge[M];
struct Bridges{
	static const int NSZ=205;
	vector<pair<int,int>> E[NSZ];
	vector<int> ans;
	int n,disc[NSZ],low[NSZ],tid;
	void init(int _n){n=_n;tid=0;ans.clear();for(int i=1;i<=n;i++)E[i].clear(),disc[i]=low[i]=0;}
	void AddEdge(int u,int v,int e){E[u].pb({v,e});E[v].pb({u,e});}
	void DFS(int u,int p){
		disc[u]=low[u]=++tid;
		for(auto e:E[u])if(e.second!=p){
			int v=e.first;
			if(!disc[v]){
				DFS(v,e.second);
				if(low[v]>disc[u])ans.pb(e.second);
				low[u]=min(low[u],low[v]);
			}else low[u]=min(low[u],disc[v]);
		}
	}
}GPH;
void FindBridges(vector<pair<int,int>> go[],int st,int n){
	GPH.init(n);
	vector<bool> was(n+1,0);
	function<void(int)> CNS=[&](int u){
		was[u]=1;
		for(auto e:go[u]){
			GPH.AddEdge(u,e.first,e.second);
			if(!was[e.first])CNS(e.first);
		}
	};
	CNS(st);
	GPH.DFS(st,-1);
	//printf(":D\n");
	for(int i:GPH.ans)bridge[i]=1;
}
void Dijkstra(vector<pair<int,int>> E[],int n,int st,int dist[],vector<pair<int,int>> go[],bool g=0){
	for(int i=1;i<=n;i++)dist[i]=inf,go[i].clear();
	set<pair<int,int>> pq;
	dist[st]=0;pq.insert({0,st});
	while(!pq.empty()){
		int u=pq.begin()->second;
		int d=pq.begin()->first;
		pq.erase(pq.begin());
		if(dist[u]!=d)continue;
		for(auto e:E[u]){
			int v=e.first,w=edges[e.second].c;
			if(dist[v]>dist[u]+w){
				if(dist[v]!=inf)pq.erase({dist[v],v});
				dist[v]=dist[u]+w;
				if(g)go[v].clear();
				pq.insert({dist[v],v});
			}
			if(g && dist[v]==dist[u]+w)go[v].pb({u,e.second});
		}
	}
}
vector<pair<int,int>> E[N],R[N],T[N],go[N];
void BuildRev(int j,int m,int n){
	for(int i=1;i<=n;i++)T[i].clear();
	for(int i=1;i<=m;i++){
		if(i!=j)T[edges[i].u].pb({edges[i].v,i});
		else T[edges[i].v].pb({edges[i].u,i});
	}
}
int dist[2][2][N],tmp[N];
int main(){
	int n,m;
	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].pb({edges[i].v,i});
		R[edges[i].v].pb({edges[i].u,i});
	}
	Dijkstra(E,n,1,dist[0][0],go,1);
	FindBridges(go,n,n);
	Dijkstra(R,n,n,dist[0][1],go);
	Dijkstra(E,n,n,dist[1][0],go,1);
	FindBridges(go,1,n);
	Dijkstra(R,n,1,dist[1][1],go);
	ll ans=(ll)dist[0][0][n]+dist[1][0][1];
	for(int i=1;i<=m;i++){
		if(bridge[i]){
			BuildRev(i,m,n);
			Dijkstra(T,n,1,tmp,go);
			ll now=tmp[n];
			if(now==inf)continue;
			//printf("%i ",tmp[n]);
			Dijkstra(T,n,n,tmp,go);
			now+=tmp[1];
			//printf("%i ",tmp[1]);
			now+=edges[i].d;
			ans=min(ans,now);
			//printf("%i %lld\n",i,now);
		}else{
			int u=edges[i].u,v=edges[i].v,c=edges[i].c,d=edges[i].d;
			ll d1=dist[0][0][n];
			if(dist[0][0][v]<dist[0][0][u])d1=min(d1,(ll)dist[0][0][v]+c+dist[0][1][u]);
			ll d2=dist[1][0][1];
			if(dist[1][0][v]<dist[1][0][u])d2=min(d2,(ll)dist[1][0][v]+c+dist[1][1][u]);
			ans=min(ans,d1+d2+d);
		}
	}
	if(ans<inf)printf("%lld\n",ans);
	else printf("-1\n");
	return 0;
}

Compilation message (stderr)

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

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