Submission #205361

#	Time	Username	Problem	Language	Result	Execution time	Memory
205361		TadijaSebez	Olympic Bus (JOI20_ho_t4)	C++11	100 / 100	396 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;
}
struct DijkstraPQ{
	static const int N=205;
	int a[N],idx[N],val[N],n;
	void init(int _n,int st,int inf){
		n=_n;
		for(int i=1;i<=n;i++)a[i]=i,val[i]=inf;
		swap(a[st],a[1]);
		for(int i=1;i<=n;i++)idx[a[i]]=i;
		val[st]=0;
	}
	int size(){return n;}
	void Change(int x,int f){
		val[x]=f;
		int p=idx[x];
		while(p>1 && f<val[a[p/2]])a[p]=a[p/2],idx[a[p]]=p,p/=2;
		a[p]=x;idx[x]=p;
	}
	int top(){return a[1];}
	void pop(){
		int now=1;
		a[1]=a[n];n--;
		idx[a[1]]=1;
		while(now*2<=n){
			int ch=now*2;
			if(ch+1<=n && val[a[ch+1]]<val[a[ch]])ch++;
			if(val[a[now]]<=val[a[ch]])break;
			swap(a[now],a[ch]);
			idx[a[now]]=now;
			idx[a[ch]]=ch;
			now=ch;
		}
	}
};
void Dijkstra(vector<pair<int,int>> E[],int n,int st,int dist[],vector<pair<int,int>> go[]){
	for(int i=1;i<=n;i++)dist[i]=inf,go[i].clear();
	DijkstraPQ pq;pq.init(n,st,inf);
	dist[st]=0;
	while(pq.size()){
		int u=pq.top();
		pq.pop();
		for(auto e:E[u]){
			int v=e.first,w=edges[e.second].c;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				go[v].clear();
				//pq.push({-dist[v],v});
				pq.Change(v,dist[v]);
			}
			if(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);
	FindBridges(go,n,n);
	Dijkstra(R,n,n,dist[0][1],go);
	Dijkstra(E,n,n,dist[1][0],go);
	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:108: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:110: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: 63 / 63