글 읽기 - 50퍼센트에서 틀리는데요

tmd3283 5년 전 1

질문에 올라온 알고리즘 대로 구현했습니다.

가중치를 모두 2배하고 속도가 두배일 때는 가중치의 /2하고 속도가 느릴 때는 가중치의 *2로 해서 dijkstra로 구현했습니다.

이때 dist2의 배열을 이차원으로 해서 dist2[here][0]은 짝수번의 edge를 통해서 왔다는 것이고

dist2[here][1]은 홀수번의 edge를 통해서 왔다는 의미입니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <memory.h>
#include <string>
#include <functional>
#include <memory.h>
#include <string.h>
#include <stack>
using namespace std;
using lint = long long;
using ii = pair<lint, int>;
const lint INF = numeric_limits<lint>::max();
int N, M;
vector<ii>adj[4001];
vector<lint> dijkstra(int start) {
	vector<lint>dist(N, INF);
	dist[start] = 0;
	priority_queue<ii>pq;
	pq.push(ii(0, start));
	while (!pq.empty()) {
		int here = pq.top().second;
		lint cost = -pq.top().first;
		pq.pop();
		if (dist[here] < cost)continue;
		for (auto&it : adj[here]) {
			int there = it.first;
			lint therecost = cost +1LL* it.second;
			if (dist[there] > therecost) {
				dist[there] = therecost;
				pq.push(ii(-therecost, there));
			}
		}
	}
	return dist;
}
lint dist2[4001][2];
//dist2[here][1]:here까지 홀수번의 edge를 통해서 왔다.
//dist2[here][0]:here까지 짝수번의 edge를 통해서 왔다.
void dijkstra1(int start) {
	for (int i = 0; i < N; i++) {
		dist2[i][0] = dist2[i][1] = INF;
	}
	dist2[start][0]=dist2[start][1] = 0;
	priority_queue<pair<lint,pair<int,int>>>pq;
	pq.push(make_pair(0, make_pair(start, 0)));
	while (!pq.empty()) {
		lint cost = -pq.top().first;
		int here = pq.top().second.first;
		int cnt = pq.top().second.second;
		pq.pop();
		if (dist2[here][cnt] < cost)continue;
		for (auto&it : adj[here]) {
			int there = it.first;
			lint therecost = 1LL*cost;
			if (!cnt)
				therecost += 1LL*it.second / 2;
			else
				therecost += 1LL*it.second * 2;
			if (dist2[there][!cnt] > therecost) {
				dist2[there][!cnt] = therecost;
				pq.push(make_pair(-therecost, make_pair(there, !cnt)));
			}

		}
	}
	return;
}
int main(void) {
	int from, to,val;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &from, &to,&val);
		from--, to--;
		adj[from].push_back(ii(to,2*val));
		adj[to].push_back(ii(from,2*val));
	}
	vector<lint>dist1 = dijkstra(0);
	dijkstra1(0);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (dist1[i] == INF)continue;
		if (dist1[i] < min(dist2[i][0], dist2[i][1]))ans++;
	}
	printf("%d\n", ans);
	return 0;
}

ryute 5년 전 2

47번째 줄에서 두 정점의 거리를 모두 0으로 초기화하면 안 됩니다. 한 바퀴 돌아서 정점 1으로 이동 한 다음 길/짧으로 이동하는 것이 최적일 수도 있습니다.

tmd3283 5년 전 0

47번째 줄은 늑대의 다익스트라인데 정점을.모두 1씩 빼서 시작점 1이 0으로 했는데요

이 때 한바퀴를 돌아서 가는.것이 최적인 경우가 있나요??

tmd3283 5년 전 2

고민하다가 깨달았습니다.

만약 input이

5 5

1 2 1

1 4 5

1 5 3

4 5 4

2 3 400

으로 주어진다면 3까지의 최단거리를 dist2[start][1]=0으로 한다면 잘못 구하게 됩니다.

감사합니다.

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

문제

문제

출처

ICPC

50퍼센트에서 틀리는데요

tmd3283 5년 전 1

ryute 5년 전 2

tmd3283 5년 전 0

tmd3283 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말