제출 #671617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671617		Baytoro	Evacuation plan (IZhO18_plan)	C++17	10 / 100	4073 ms	22948 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e9+9,mod=1e9+7;
struct edge{
	int a,b,c;
};
vector<pair<int,int>> g[100005];
vector<int> dist(100005,INF),p(100005),sz(100005),ed[100005];
int f(int x){
	if(p[x]==x) return x;
	return p[x]=f(p[x]);
}
void un(int a, int b){
	int ta=a,tb=b;
	a=f(a),b=f(b);
	if(a==b) return;
	if(sz[a]>sz[b]) swap(a,b);
	ed[ta].pb(tb);
	ed[tb].pb(ta);
	p[a]=b;
	sz[b]+=sz[a];
}
int dfs(int x, int p, int y){
	if(x==y) return dist[x];
	int ret=INF;
	for(auto it: ed[x]){
		if(it==p) continue;
		int k=dfs(it,x,y);
		if(k!=INF){
			return min(dfs(it,x,y),dist[x]);
		}
	}
	
	return INF;
}
int n,m;
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
		sz[i]=1;
	}
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		g[a].pb({b,c});
		g[b].pb({a,c});
	}
	int k;cin>>k;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> dq;
	for(int i=0;i<k;i++){
		int x;
		cin>>x;
		dq.push({0,x});
		dist[x]=0;
	}
	while(!dq.empty()){
		pair<int,int> a=dq.top();
		dq.pop();
		if(dist[a.sc]<a.fr) continue;
		for(auto it: g[a.sc]){
			if(dist[it.fr]<=it.sc+a.fr) continue;
			else{
				dist[it.fr]=it.sc+a.fr;
				dq.push({dist[it.fr],it.fr});
			}
		}
	}
	vector<pair<int,int>> vec;
	for(int i=1;i<=n;i++){
		vec.pb({dist[i],i});
	}
	/*for(int i=0;i<n;i++){
		cout<<vec[i].fr<<' ';
	}*/
	sort(rall(vec));
	for(int i=0;i<n;i++){
		for(auto it: g[vec[i].sc]){
			un(vec[i].sc,it.fr);
		}
	}
	int q;
	cin>>q;
	while(q--){
		int a,b;cin>>a>>b;
		cout<<dfs(a,-1,b)<<endl;
	}
}
main(){
	ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

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

plan.cpp: In function 'long long int dfs(long long int, long long int, long long int)':
plan.cpp:37:6: warning: unused variable 'ret' [-Wunused-variable]
   37 |  int ret=INF;
      |      ^~~
plan.cpp: At global scope:
plan.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){
      | ^~~~
plan.cpp: In function 'void fopn(std::string)':
plan.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46