제출 #434730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434730		chirathnirodha	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2090 ms	22184 KiB

commuter_pass

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define ER erase
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int n,m,s,t,u,v;
vector<pair<ll,ll> > adj[100000];
vector<ll> dps,dpu,dpv;
multiset<ll> minu,minv;
vector<ll> dijkstra(int a){
	vector<ll> dp;
	for(int i=0;i<n;i++)dp.PB(INT64_MAX);
	dp[a]=0;
	priority_queue<pair<ll,ll> > q;
	q.P(MP(0,a));
	while(!q.empty()){
		pair<ll,ll> c=q.top();q.pop();
		for(int i=0;i<adj[c.S].size();i++){
			ll x=adj[c.S][i].F,y=adj[c.S][i].S;
			if(dp[x]>dp[c.S]+y){
				dp[x]=dp[c.S]+y;
				q.P(MP(-dp[x],x));
			}
		}
	}
	return dp;
}
ll ans;
void dfs(int x){
	if(x==0){
		ans=min(ans,*minu.begin()+*minv.begin());
		return;
	}
	for(int i=0;i<adj[x].size();i++){
		ll a=adj[x][i].F,b=adj[x][i].S;
		if(dps[x]==dps[a]+b){
			minv.I(dpv[a]);
			minu.I(dpu[a]);
			dfs(a);
			minu.ER(minu.find(dpu[a]));
			minv.ER(minv.find(dpv[a]));
		}
	}
}
void solve(){
    cin>>n>>m>>s>>t>>u>>v;
	s--;t--;u--;v--;
	for(int i=0;i<m;i++){
		ll x,y,z;cin>>x>>y>>z;x--;y--;
		adj[x].PB(MP(y,z));adj[y].PB(MP(x,z));
	}
	dps=dijkstra(s);
	dpu=dijkstra(u);
	dpv=dijkstra(v);
	for(int i=0;i<n;i++)cout<<dps[i]<<" ";cout<<endl;
	for(int i=0;i<n;i++)cout<<dpu[i]<<" ";cout<<endl;
	for(int i=0;i<n;i++)cout<<dpv[i]<<" ";cout<<endl;
	ans=dpu[v];
	minu.I(dpu[t]);
	minv.I(dpv[t]);
	dfs(t);
	cout<<ans;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int)':
commuter_pass.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<adj[c.S].size();i++){
      |               ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<adj[x].size();i++){
      |              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:72:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   72 |  for(int i=0;i<n;i++)cout<<dps[i]<<" ";cout<<endl;
      |  ^~~
commuter_pass.cpp:72:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |  for(int i=0;i<n;i++)cout<<dps[i]<<" ";cout<<endl;
      |                                        ^~~~
commuter_pass.cpp:73:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   73 |  for(int i=0;i<n;i++)cout<<dpu[i]<<" ";cout<<endl;
      |  ^~~
commuter_pass.cpp:73:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |  for(int i=0;i<n;i++)cout<<dpu[i]<<" ";cout<<endl;
      |                                        ^~~~
commuter_pass.cpp:74:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |  for(int i=0;i<n;i++)cout<<dpv[i]<<" ";cout<<endl;
      |  ^~~
commuter_pass.cpp:74:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |  for(int i=0;i<n;i++)cout<<dpv[i]<<" ";cout<<endl;
      |                                        ^~~~

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