글 읽기 - 50%에서 틀리는데 어디가 틀렸는지 봐주실 수 있나요?

lstwinsj3 2년 전 0

여우(fd) 와 늑대(wd)로 각각 다익스트라 알고리즘을 통해 최단 거리를 구하고 여우가 더 빨리 도착하는 경우를 셉니다. 늑대의 경우 ff로 다음에 빠르게 갈지/느리게 갈지를 저장하였습니다.. 예제도 몇 개 돌려봤는데 다 맞는 것 같은데ㅠㅠ 혹시 반례 찾아주실 수 있나요? 감사합니다...

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int N,M,ans;
long long fd[4001],wd[2][4001];
vector<pair<int,long long> > adj[4001];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	while(M--){
		int a,b,c;
		cin>>a>>b>>c;
		--a,--b;
		c*=2;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	for(int i=0;i<N;++i)
		fd[i]=wd[0][i]=wd[1][i]=-1;
	priority_queue<pair<long long,int> > pq;
	pq.push({0,0});
	fd[0]=0;
	while(!pq.empty()){
		long long cost=-pq.top().first;
		int now=pq.top().second;
		pq.pop();
		if(fd[now]<cost) continue;
		for(int i=0;i<adj[now].size();++i){
			int next=adj[now][i].first;
			long long ncost=adj[now][i].second;
			if(fd[next]==-1||fd[next]>cost+ncost){
				fd[next]=cost+ncost;
				pq.push({-(cost+ncost),next});
			}
		}
	}
	priority_queue<pair<long long,pair<int,bool> > > pq2;
	pq2.push({0,{0,true}});
	wd[0][0]=0;
	while(!pq2.empty()){
		long long cost=-pq2.top().first;
		int now=pq2.top().second.first;
		bool ff=pq2.top().second.second;
		pq2.pop();
		if(wd[!ff][now]<cost) continue;
		for(int i=0;i<adj[now].size();++i){
			int next=adj[now][i].first;
			long long ncost=adj[now][i].second;
			if(ff) ncost/=2;
			else ncost*=2;
			if(wd[ff][next]==-1||wd[ff][next]>cost+ncost){
				wd[ff][next]=cost+ncost;
				pq2.push({-(cost+ncost),{next,!ff}});
			}
		}
	}
	for(int i=0;i<N;++i)
		if((fd[i]!=-1&&wd[0][i]!=-1&&fd[i]<wd[0][i])&&(fd[i]!=-1&&wd[1][i]!=-1&&fd[i]<wd[1][i]))
			++ans;
	cout<<ans<<'\n';
}

rudgus06 4달 전 0

늑대가 다시 시작점으로 뛰어서 들어올 경우의 수가 있네요 그래서 시작점을 0으로 초기화 하시면 안 될 것 같아요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

50%에서 틀리는데 어디가 틀렸는지 봐주실 수 있나요?

lstwinsj3 2년 전 0

rudgus06 4달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말