글 읽기 - 50%에서 틀리네요. 도와주세요.

cgy7096 6년 전 0

50%에서 자꾸 틀려요.

고수님들. 도와주세요.

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

#define INF 98765432
double adj[201][201] = { 0, };
double dist[201] = { 0, };
int T = 0, N = 0, M = 0, S = 0, D = 0, ai = 0, bi = 0, ci = 0, di = 0;
double  s = 0, p = 0, y = 0;

double dijk(int a, int b) {
	priority_queue <pair <double, int>, vector <pair <double, int> >, greater <pair <double, int> > > que;
	que.push(make_pair(0, a));
	for (int i = 0; i <= N; ++i)
		dist[i] = INF;
	dist[a] = 0;
	while (!que.empty()) {
		int here = (que.top()).second;
		que.pop();
		for (int i = 1; i <= N; ++i) {
			if (adj[here][i] > 0 && dist[i] > dist[here] + adj[here][i]) {
				dist[i] = dist[here] + adj[here][i];
				que.push(make_pair(dist[i], i));
			}
		}
	}
	return dist[b];
}

int main() {
	cin >> T;
	for (int ct = 0; ct < T; ++ct) {
        memset(adj, 0, sizeof(adj));
		cin >> N >> M >> S >> D >> s >> p >> y;
		for (int i = 0; i < M; ++i) {
			cin >> ai >> bi >> ci >> di;
			double w = min(s + p * di, (ci * 0.01) * (y + p * di));
			adj[ai][bi] = adj[bi][ai] = w;
		}

		cout << fixed;
		cout.precision(2);
		cout << dijk(S, D) << endl;
	}

	return 0;
}

juhongkim2 6년 전 0

저도 처음에는 각 간선마다 Min(요금지불의 기대값,무임승차의 기대값)의 가중치를 두고 다익스트라를 썼는데 똑같이 50에서 틀리더군요

반례

3 2 1 3 10 1 100

1 2 50 90

2 3 90 10

답 : 110.00

작성자님 소스로는 115.00이 나옵니다

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

문제

문제

출처

ICPC

50%에서 틀리네요. 도와주세요.

cgy7096 6년 전 0

juhongkim2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말