\# 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

    
    
    
    
3 2 1 2 5 6 2 3 4 5 1 3 0 0

 
Sample Output

    
    
    
    
9 11

 
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 << "
"; } }

좋은 웹페이지 즐겨찾기