\# HDU 3790 최 단 경로 문제 [Dijkstra 입문 문제]

제목:
질문
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19767 Accepted Submission(s): 5880
Problem Description
n 개의 점 을 드 리 겠 습 니 다. m 개의 방향 이 없고 모든 변 에 길이 d 와 소비 p 가 있 습 니 다. 출발점 s 종점 t 를 드 리 겠 습 니 다. 출력 출발점 에서 종점 까지 의 최 단 거리 와 비용 을 요구 합 니 다. 만약 에 최 단 거리 에 여러 노선 이 있 으 면 수출 비용 이 가장 적 습 니 다.

Input
n, m 를 입력 하 십시오. 점 의 번 호 는 1 ~ n 이 고 그 다음 에 m 줄 입 니 다. 줄 마다 4 개의 숫자 a, b, d, p 는 a 와 b 사이 에 한 변 이 있 고 그 길 이 는 d 이 며 비용 은 p 입 니 다.마지막 줄 은 두 개의 수 s, t 이다.기점 s, 종점.n 과 m 가 0 일 때 입력 이 끝 납 니 다.
(1
Output
한 줄 을 출력 하 는 데 는 두 개의 수가 있 는데, 가장 짧 은 거리 와 비용 이 든다.

Sample Input

Sample Output

Source
저장 성 컴퓨터 대학원 재시험
제목 이 간단 하 다.
표준 Dijkstra, 거리 값 을 업데이트 할 때 가격 을 동시에 업데이트 하고 마지막 에 함께 출력 하 는 것 을 주의 하 십시오.
데이터 에 구덩이 가 없다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<math.h>
#include<vector>

using namespace std;

struct node{
	int ans = 0;
	int vis = 0;
	int minr = 1e9;
	vector<int>con;
	vector<int>len;
	vector<int>exp;
}data[2005];

int main()
{
	int n, m, begi, endi;
	while (cin >> n >> m)
	{
		if (n == 0 && m == 0)
		{
			return 0;
		}
		for (size_t i = 0; i <= n; i++)
		{
			data[i].ans = 0;
			data[i].vis = 0;
			data[i].minr = 1e9;
			data[i].con.clear();
			data[i].len.clear();
			data[i].exp.clear();
		}
		for (size_t i = 0; i < m; i++)
		{
			int be, ed, len, tar;
			scanf("%d%d%d%d", &be, &ed, &len, &tar);
			data[be].con.push_back(ed);
			data[be].len.push_back(len);
			data[ed].con.push_back(be);
			data[ed].len.push_back(len);
			data[be].exp.push_back(tar);
			data[ed].exp.push_back(tar);
		}
		cin >> begi >> endi;
		data[begi].ans = 0;
		data[begi].minr = 0;
		while (1)
		{
			if (begi == endi)
			{
				break;
			}
			int size = data[begi].con.size();
			for (size_t i = 0; i < size; i++)
			{
				if (data[data[begi].con[i]].minr > data[begi].minr + data[begi].len[i])
				{
					data[data[begi].con[i]].ans = data[begi].ans + data[begi].exp[i];
					data[data[begi].con[i]].minr = data[begi].minr + data[begi].len[i];
				}
				else if (data[data[begi].con[i]].minr == data[begi].minr + data[begi].len[i])
				{
					data[data[begi].con[i]].ans = min(data[begi].ans + data[begi].exp[i], data[data[begi].con[i]].ans);
				}
			}
			data[begi].vis = 1;
			int temp = 1e9;
			begi = -1;
			for (size_t i = 1; i <= n; i++)
			{
				if (temp>data[i].minr&&data[i].vis == 0)
				{
					temp = data[i].minr;
					begi = i;
				}
			}
			if (begi == -1)
			{
				break;
			}
		}
		cout << data[endi].minr << " " << data[endi].ans << "
";
	}

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

물체 검출의 평가 지표 IoU의 계산 방법

Yolo나 SSD 등 물체 검출에서 평가 지표로 사용되는 IoU에 대해 조사했으므로 정리했습니다. IoU (Intersection over Union)는 두 영역이 얼마나 겹치는지를 나타내는 지표입니다. 두 영역의 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

\# HDU 3790 최 단 경로 문제 [Dijkstra 입문 문제]

좋은 웹페이지 즐겨찾기