\# 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 << "
";
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.