제출 #1170726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170726		jellybean	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	8 ms	840 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define dd(x) cout<<#x<<" is "<<x<<endl;

const int N = 3005;
vector<pii>adj[N];
int dis[N];
int dis1[N];
const int inf = 1e16;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n,m; cin>>n>>m;
	int s,t,l,k; cin>>s>>t>>l>>k;
	for(int i=0; i<m; i++){
		int a,b,c; cin>>a>>b>>c;
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=0; i<=n; i++) dis[i] = inf;
	dis[s] = 0;
	pq.push({0,s});
	while(!pq.empty()){
		auto[d,x] = pq.top(); pq.pop();
		if(d!=dis[x]) continue;
		for(auto [i,w]: adj[x]){
			if(dis[i] == inf or dis[i] > d+w){
				dis[i] = d+w;
				pq.push({d+w,i});
			}
		}
	}
	
	//for(int i=1; i<=n; i++) cout<<dis[i]<<" ";
	//cout<<endl;
	
	priority_queue<pii,vector<pii>,greater<pii>>pq1;
	for(int i=0; i<=n; i++) dis1[i] = inf;
	dis1[t] = 0;
	pq1.push({0,t});
	while(!pq1.empty()){
		auto[d,x] = pq1.top(); pq1.pop();
		if(d!=dis1[x]) continue;
		for(auto [i,w]: adj[x]){
			if(dis1[i] == inf or dis1[i] > d+w){
				dis1[i] = d+w;
				pq1.push({d+w,i});
			}
		}
	}
	
	//dd(dis[t])
	
	if(dis[t] <= k){
		cout<<n*(n-1)/2;
		//dd(1)
		return 0;
	}
	int ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(dis[i] + l + dis1[j] <= k) ans++;
		}
	}
	cout<<ans;
	
	
	
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 0 / 47