uva 10986 - 이메일 보내기(최단 Dijkstra)
2192 단어 dijkstra
제목 대의: n, m, s, t, n을 제시하면 n개의 점이 있고 m는 m개의 변이 있음을 나타낸다. 그리고 m행 데이터를 제시하면 m개의 변이 있다. 각 변의 데이터는 두 개의 번호와 이 변의 권한이 연결되어 있다. 점 s에서 점 t까지의 가장 짧은 경로가 얼마냐고 묻는다.
문제 풀이 사고방식: 본고는 무환정권치의 한 그림이어야 한다. 그리고 본고는 Dijkstra 알고리즘으로 직접 하면 시간을 초과하기 때문에 반드시 우선 대기열로 최적화를 해야 한다. 에서 이런 방법을 소개했는데 유일하게 변동된 점은 유방향도가 무방향도가 되었다는 것이다.
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using std::make_pair;
using namespace std;
const int N = 400005;
const int INF = 1 << 30;
typedef pair<int, int> pii;
int n, m, s, t;
int d[N], rec[N];
int first[N], u[N], next[N], v[N], w[N];
struct cmp {
bool operator () (const int a, const int b) {
return a % 10 > b % 10;
}
};
priority_queue<pii, vector<pii>, greater<pii> > q;
void init() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 0; i < n; i++) first[i] = -1;
int a, b;
m *= 2;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u[i], &v[i], &w[i]);
next[i] = first[u[i]];
first[u[i]] = i;
i++;
v[i] = u[i - 1], u[i] = v[i - 1], w[i] = w[i - 1];
next[i] = first[u[i]];
first[u[i]] = i;
}
}
void dijkstra() {
bool rec[N];
for (int i = 0; i < n; i++) d[i] = (i == s ? 0 : INF);
memset(rec, 0, sizeof(rec));
q.push(make_pair(d[s], s));
while (!q.empty()) {
pii f = q.top();
q.pop();
int x = f.second;
if (rec[x]) continue;
rec[x] = 1;
for (int e = first[x]; e != -1; e = next[e]) {
if (d[v[e]] > d[x] + w[e]) {
d[v[e]] = d[x] + w[e];
q.push(make_pair(d[v[e]], v[e]));
}
}
}
}
int main () {
int cas, ti = 1;
scanf("%d", &cas);
while (cas--) {
init();
dijkstra();
printf("Case #%d: ", ti++);
if (d[t] == INF)
printf("unreachable
");
else
printf("%d
", d[t]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준]#11779 최소비용 구하기 2n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.