글 읽기 - 솔루션에 대한 질문입니다

p_ce1052 3년 전 0

1.솔루션에서 어떤 정점 C에 T를 연결해서 이득보는 거리를 각각 구해주던데 C에 T를 연결하는 바람에 C를 거치지 않던 다른 정점에서 C를 거치는 것이 최단경로가 되어버리는 상황이 있을 수 있지 않나요? 이런 경우가 있는데 어떻게 처음 그래프에서 최단경로와 해당 정점을 거치는 소의 숫자를 미리 구해놓고 T를 연결해서 답을 구하는지 모르겠습니다. 원래 그래프에서는 C를 안거치던 정점이 T를 연결하면서 C를 거치게 되면 구해놓은 값들이 바뀌지 않나요?

2. 1번 물음을 제쳐두고 구현을 했는데 틀렸습니다를 받네요 어디가 잘못되었는지 알 수 있을까요?

다익스트라로 최단거리 구해놓고 가장 먼 노드에서부터 다음 노드로 현재 정점을 거치는 소의 수를 다음 정점에 더해주었습니다. 사전순 PATH로 이동하기 위해 간선을 전부 정렬했습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
ll n,m,t;
ll dist[10005];
vector<pi>graph[10005];
ll arr[10005];
bool visited[10005];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("shortcut.in","r",stdin);
	//freopen("shortcut.out","w",stdout);
	
	cin>>n>>m>>t;
	for(int i=1; i<=n; i++) cin>>arr[i];
	while(m--){
		ll a,b,w;
		cin>>a>>b>>w;
		graph[a].push_back(pi(b,w));
		graph[b].push_back(pi(a,w));
	}
	priority_queue<pi,vector<pi>,greater<pi> >pq;
	for(int i=1; i<=n; i++) dist[i] = INT64_MAX;
	dist[1] = 0;
	pq.push(pi(dist[1],1));
	while(!pq.empty()){
		ll cur = pq.top().second;
		ll d = pq.top().first;
		pq.pop();
		if(dist[cur]<d) continue;
		for(pi a : graph[cur]){
			int nxt = a.first;
			ll w = a.second;
			if(dist[nxt]>dist[cur]+w){
				dist[nxt] = dist[cur]+w;
				pq.push(pi(dist[nxt],nxt));
			}
		}
	}
	for(int i=1; i<=n; i++) sort(graph[i].begin(),graph[i].end());
	priority_queue<pi,vector<pi>,less<pi> >pq2;
	for(int i=1; i<=n; i++) pq2.push(pi(dist[i],i));
	while(!pq2.empty()){
		int cur = pq.top().second;
		pq2.pop();
		for(int i=0; i<graph[cur].size(); i++){
			int nxt = graph[cur][i].first;
			ll w = graph[cur][i].second;
			if(dist[nxt]+w==dist[cur]){
				arr[nxt]+=arr[cur];
				break;
			}
		}
	}
	ll mx = 0;
	for(int i=2; i<=n; i++){
		if(dist[i]>t){
			mx = max(mx,arr[i]*(dist[i]-t));
		}
	}
	cout<<mx;
}

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

문제

문제

출처

ICPC

솔루션에 대한 질문입니다

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말