Submission #231133

#	Time	Username	Problem	Language	Result	Execution time	Memory
231133		nafis_shifat	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	474 ms	26580 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]={};
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);
	
	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);
	}

}

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];
	dfs(S,inf,inf);

	printf("%lld",ans);

	

	








}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, long long int*)':
commuter_pass.cpp:33: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:57: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:67: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:69: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:75: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: 0 / 24
• Subtask 4: 0 / 45