Submission #231468

#	Time	Username	Problem	Language	Result	Execution time	Memory
231468		nafis_shifat	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	487 ms	28892 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const ll inf=1e18;
vector<int> adj[mxn];
 
vector <ll> cost[mxn];
 
ll d1[mxn],d2[mxn],d3[mxn],d4[mxn];
 
ll z;
ll ans;
int us[mxn]={};
ll minX[mxn],minY[mxn];
void dijkstra(int src,ll dist[]) {
	for(int i=1;i<mxn;i++)dist[i]=inf;
 
	dist[src]=0;
    
    priority_queue<pair<ll,int>> pq;
    pq.push({0,src});
 
    int vis[mxn]={};
 
    while(!pq.empty()) {
        
    	int u=pq.top().second;
    	pq.pop();
 
    	if(vis[u])continue;
    	vis[u]=1;
    	for(int i=0;i<adj[u].size();i++) {
    		int v=adj[u][i];
    		if(dist[u]+cost[u][i]<dist[v]) {
    			dist[v]=dist[u]+cost[u][i];
    			pq.push({-dist[v],v});
    		}
    	}
    }
 
}
 
 
void dfs(int cur,ll x,ll y) {
    
    x=min(x,d2[cur]);
	y=min(y,d3[cur]);
	
	ans=min(ans,x+y);
	ans=min(ans,x+minY[cur]);
	ans=min(ans,y+minX[cur]);
	
	if(us[cur])return;
    us[cur]=1;
 
	for(int i=0;i<adj[cur].size();i++) {
		int v=adj[cur][i];
		
 
		if(d1[cur]+cost[cur][i]+d4[v]==z) {
		     dfs(v,x,y);
		     minX[cur]=min(minX[cur],minX[v]);
		     minY[cur]=min(minY[cur],minY[v]);
		     
		}
	}
 
}
 
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	int S,T,U,V;
	scanf("%d%d%d%d",&S,&T,&U,&V);
 
	for(int i=0;i<m;i++)
	{
		int u,v;
		ll w;
		scanf("%d %d %lld",&u,&v,&w);
 
		adj[u].push_back(v);
		adj[v].push_back(u);
		cost[u].push_back(w);
		cost[v].push_back(w);
	}
 
	
	dijkstra(S,d1);
	dijkstra(T,d4);
	dijkstra(U,d2);
	dijkstra(V,d3);
	z=d1[T];
	ans=d2[V];
	
	for(int i=1;i<=n;i++)minX[i]=d2[i],minY[i]=d3[i];
	dfs(S,inf,inf);
 
	printf("%lld",ans);
 
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, long long int*)':
commuter_pass.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<adj[u].size();i++) {
                  ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int, long long int, long long int)':
commuter_pass.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[cur].size();i++) {
              ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
commuter_pass.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&S,&T,&U,&V);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45