글 읽기 - 무임승차 50% 도와주세요! 고수님들!!!

QuqqU 6년 전 0

각 지점에 대해서,

각 지점을 요금을 내고 도착할 경우를 dp[][0]으로

각 지점을 무임승차하는 경우를 dp[][1]로 저장했습니다.

//////////////////////////////////////////////////

dp[curr][0]에서 dp[next][0]으로 가는 경로는

dp[next][0] = dp[curr][0] + (기본 요금 s가 포함되지 않는) 거리당 요금 p * 거리 d

dp[curr][1]에서 dp[next][0]으로 가는 경로는

dp[next][0] = dp[curr][1] + (기본 요금 s를 포함하는) s + p * d

dp[curr][]에서 dp[next][1]로 가는 것은

dp[next][1] = dp[curr][] + (double)(y + p*d) * (확률 퍼센트단위) c / 100.0

//////////////////////////////////////////////////

dp[][0]과 dp[][1] 둘 중 작은 값을 dist에 저장하고

pq에 넣었는데 틀렸다고 합니다(50 % )

도와주세요!

/////////////////

예외라도 찾는 데 도와주신다면 감사드립니다 ㅠㅠ..

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#define INF 999999999999999999
using namespace std;
typedef pair<long long int, long long int> ii;
typedef pair<double, long long int> di;
typedef pair<long long int, ii> intii;


double dp[205][5];
priority_queue<di, vector<di>, greater<di>> pq;

int main() {
	int testcase; scanf("%d", &testcase);
	for (long long int i = 0; i < testcase; i++) {
		vector<intii> edge[205], buf;
		vector<double> dist(205, INF);
		vector<bool> visited(205, false);
		long long int n, m, start, end, s, p, y; scanf("%lld %lld %lld %lld %lld %lld %lld", &n, &m, &start, &end, &s, &p, &y);
		for (long long int i = 0; i < m; i++) {
			long long int a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
			edge[a].push_back(intii(b, ii(c, d)));
			edge[b].push_back(intii(a, ii(c, d)));//확률/거리
		}

		dp[start][0] = s;
		dp[start][1] = 0;
		dist[start] = min(dp[start][0], dp[start][1]);
		pq.push(di(dist[start], start));
		while (!pq.empty()) {
			long long int curr = pq.top().second;
			double currdist = pq.top().first;
			pq.pop();
	
			//if (dist[curr] < currdist) continue;
			if (visited[curr]) continue;
			visited[curr] = true;

			for (auto& next : edge[curr]) {
				if (visited[next.first]) continue;
				dp[next.first][0] = min(dp[curr][0] + next.second.second * p, dp[curr][1] + next.second.second * p + s);
				dp[next.first][1] = min(dp[curr][0], dp[curr][1]) + (double)(y + p*next.second.second) * next.second.first / 100.0;
				double nextdist = min(dp[next.first][0], dp[next.first][1]);
				if (dist[next.first] > nextdist) {
					dist[next.first] = nextdist;
					pq.push(di(dist[next.first], next.first));
				}
			}
		}

		printf("%.2lf\n", dist[end]);
	}


	return 0;
}

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

문제

문제

출처

ICPC

무임승차 50% 도와주세요! 고수님들!!!

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말