글 읽기 - 이문제 Dijkstra문제가 아닌가요?

ykmyou 7년 전 0

Dijkstra 알고리즘을 k-1번 사용해서
매번 못가는 경로 지정해주고 풀면 되는거 아닌가요??

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

vector<pair<long long, long long> > G[2001];
vector<long long> C;
long long dist[2001];
long long visit[2001];

void dijkstra(long long s, long long x){
	priority_queue<pair<long long, long long> > pq;
	dist[s] = 0;
	pq.push(make_pair(-dist[s], s));
	while (!pq.empty()){
		long long cur = pq.top().second;
		pq.pop();
		visit[cur] = 1;
		for (int i = 0; i < G[cur].size(); i++){
			long long next = G[cur][i].first;
			long long cost = G[cur][i].second;
			if (!(cur == C[x] && next == C[x + 1]) && !visit[next]){
				if (dist[next] == -1)
					dist[next] = dist[cur] + cost;
				else
					dist[next] = min(dist[cur] + cost, dist[next]);
				pq.push(make_pair(-dist[next], next));
			}
		}
	}
}
int main(){
	//freopen("Text.txt", "r", stdin);
	long long n, m, a, b, u, v, w, k, t;
	scanf("%lld %lld %lld %lld", &n, &m, &a, &b);
	for (long long i = 0; i < m; i++){
		scanf("%lld %lld %lld", &u, &v, &w);
		G[u].push_back(make_pair(v, w));
	}
	scanf("%lld", &k);
	for (long long i = 0; i < k; i++){
		scanf("%lld", &t);
		C.push_back(t);
	}
	for (long long i = 0; i < k - 1; i++){
		for (long long j = 1; j <= n; j++) dist[j] = -1;
		memset(visit, 0, sizeof(visit));
		dijkstra(a, i);
		printf("%lld\n", dist[b]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

이문제 Dijkstra문제가 아닌가요?

ykmyou 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말