UVA 10816 - Travel in Desert(2점+dijkstra)
UVA 10816 - Travel in Desert
제목 링크
제목: 사막에 일부 도로가 있는데 각 도로는 온도와 거리가 있다. s, t 두 점 사이의 경로를 요구하고 온도의 최대치를 충족시키며 길이가 가장 짧다.
사고방식: 2분의 온도, 그리고 dijstra는 길이를 구하면 된다.
코드:#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAXNODE = 105;
const int MAXEDGE = 20005;
typedef double Type;
const Type INF = 0x3f3f3f3f;
struct Edge {
int u, v;
Type dist, d;
Edge() {}
Edge(int u, int v, Type dist, Type d = 0) {
this->u = u;
this->v = v;
this->dist = dist;
this->d = d;
}
void read() {
scanf("%d%d%lf%lf", &u, &v, &d, &dist);
u--; v--;
}
};
struct HeapNode {
Type d;
int u;
HeapNode() {}
HeapNode(Type d, int u) {
this->d = d;
this->u = u;
}
bool operator < (const HeapNode& c) const {
return d > c.d;
}
};
int n, m, s, t;
struct Dijkstra {
int n, m;
Edge edges[MAXEDGE];
int first[MAXNODE];
int next[MAXEDGE];
bool done[MAXNODE];
Type d[MAXNODE];
int p[MAXNODE];
void init(int n) {
this->n = n;
memset(first, -1, sizeof(first));
m = 0;
}
void add_Edge(int u, int v, Type dist) {
edges[m] = Edge(u, v, dist);
next[m] = first[u];
first[u] = m++;
}
void add_Edge(Edge e) {
edges[m] = e;
next[m] = first[e.u];
first[e.u] = m++;
}
void print(int e) {//shun xu
if (p[e] == -1) {
printf("%d", e + 1);
return;
}
print(edges[p[e]].u);
printf(" %d", e + 1);
}
void print2(int e) {//ni xu
if (p[e] == -1) {
printf("%d
", e + 1);
return;
}
printf("%d ", e + 1);
print2(edges[p[e]].u);
}
bool dijkstra(int s, int t) {
priority_queue<HeapNode> Q;
for (int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
p[s] = -1;
memset(done, false, sizeof(done));
Q.push(HeapNode(0, s));
while (!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if (u == t)
return true;
if (done[u]) continue;
done[u] = true;
for (int i = first[u]; i != -1; i = next[i]) {
Edge& e = edges[i];
if (d[e.v] > d[u] + e.dist) {
d[e.v] = d[u] + e.dist;
p[e.v] = i;
Q.push(HeapNode(d[e.v], e.v));
}
}
}
return false;
}
} gao;
Edge e[MAXEDGE];
bool judge(double mid) {
gao.init(n);
for (int i = 0; i < m; i++) {
if (e[i].d > mid) continue;
gao.add_Edge(e[i]);
gao.add_Edge(Edge(e[i].v, e[i].u, e[i].dist, e[i].d));
}
if (gao.dijkstra(s, t)) return true;
return false;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
scanf("%d%d", &s, &t);
s--; t--;
for (int i = 0; i < m; i++)
e[i].read();
double l = 20, r = 50, mid;
while (r - l > 1e-8) {
mid = (l + r) / 2;
if (judge(mid)) r = mid;
else l = mid;
}
if (judge(r)) {
gao.print(t); printf("
");
printf("%.1lf %.1lf
", gao.d[t], mid);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAXNODE = 105;
const int MAXEDGE = 20005;
typedef double Type;
const Type INF = 0x3f3f3f3f;
struct Edge {
int u, v;
Type dist, d;
Edge() {}
Edge(int u, int v, Type dist, Type d = 0) {
this->u = u;
this->v = v;
this->dist = dist;
this->d = d;
}
void read() {
scanf("%d%d%lf%lf", &u, &v, &d, &dist);
u--; v--;
}
};
struct HeapNode {
Type d;
int u;
HeapNode() {}
HeapNode(Type d, int u) {
this->d = d;
this->u = u;
}
bool operator < (const HeapNode& c) const {
return d > c.d;
}
};
int n, m, s, t;
struct Dijkstra {
int n, m;
Edge edges[MAXEDGE];
int first[MAXNODE];
int next[MAXEDGE];
bool done[MAXNODE];
Type d[MAXNODE];
int p[MAXNODE];
void init(int n) {
this->n = n;
memset(first, -1, sizeof(first));
m = 0;
}
void add_Edge(int u, int v, Type dist) {
edges[m] = Edge(u, v, dist);
next[m] = first[u];
first[u] = m++;
}
void add_Edge(Edge e) {
edges[m] = e;
next[m] = first[e.u];
first[e.u] = m++;
}
void print(int e) {//shun xu
if (p[e] == -1) {
printf("%d", e + 1);
return;
}
print(edges[p[e]].u);
printf(" %d", e + 1);
}
void print2(int e) {//ni xu
if (p[e] == -1) {
printf("%d
", e + 1);
return;
}
printf("%d ", e + 1);
print2(edges[p[e]].u);
}
bool dijkstra(int s, int t) {
priority_queue<HeapNode> Q;
for (int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
p[s] = -1;
memset(done, false, sizeof(done));
Q.push(HeapNode(0, s));
while (!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if (u == t)
return true;
if (done[u]) continue;
done[u] = true;
for (int i = first[u]; i != -1; i = next[i]) {
Edge& e = edges[i];
if (d[e.v] > d[u] + e.dist) {
d[e.v] = d[u] + e.dist;
p[e.v] = i;
Q.push(HeapNode(d[e.v], e.v));
}
}
}
return false;
}
} gao;
Edge e[MAXEDGE];
bool judge(double mid) {
gao.init(n);
for (int i = 0; i < m; i++) {
if (e[i].d > mid) continue;
gao.add_Edge(e[i]);
gao.add_Edge(Edge(e[i].v, e[i].u, e[i].dist, e[i].d));
}
if (gao.dijkstra(s, t)) return true;
return false;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
scanf("%d%d", &s, &t);
s--; t--;
for (int i = 0; i < m; i++)
e[i].read();
double l = 20, r = 50, mid;
while (r - l > 1e-8) {
mid = (l + r) / 2;
if (judge(mid)) r = mid;
else l = mid;
}
if (judge(r)) {
gao.print(t); printf("
");
printf("%.1lf %.1lf
", gao.d[t], mid);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.