題目鏈接 https://vjudge.net/problem/UVA-11374
【題意】
市民從市區去機場要走機場快線，機場快線分為經濟線和商業線兩種，你只有一張商業線車票，只能坐一站商業線，其它時候只能坐經濟線，忽略換乘時間，找到一條去機場最快的線路。
【思路】
大白書329頁例題，可以先按照經濟線建立無向圖，用dijkstra算法分別求出以起點和以終點為源點的最短路，然后依次枚舉每種經濟線，看看能不能更省時間，如果能就保留這種方案，具體細節看代碼
#include<bits/stdc++.h>
using namespace std;
const int inf =
0x3f3f3f3f;
const int maxn =
550;
const int maxk =
1050;
struct Edge {
int from, to, dist;Edge(
int f,
int t,
int d) :from(f), to(t), dist(d) {}
};
struct HeapNode {
int d, u;HeapNode(
int dd,
int uu) :d(dd), u(uu) {};
bool operator < (
const HeapNode& rhs)
const {
return d > rhs.d;}
};
struct Dijkstra {
int n, m;
vector<Edge> edges;
vector<int> g[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];
void init(
int n) {
this->n = n;
for (
int i =
0; i < n; ++i) g[i].clear(); edges.clear(); }
void add(
int from,
int to,
int dist) { edges.push_back(Edge(from, to, dist));m = edges.size();g[from].push_back(m -
1);}
void dijkstra(
int s) { priority_queue<HeapNode> que;
for (
int i =
0; i < n; ++i) d[i] = inf;d[s] =
0;
memset(done,
0,
sizeof(done));que.push(HeapNode(
0, s));
while (!que.empty()) {HeapNode x = que.top();que.pop();
int u = x.u;
if (done[u])
continue;done[u] =
true;
for (
int i =
0; i < g[u].size(); ++i) {Edge& e = edges[g[u][i]];
if (d[e.to] > d[u] + e.dist) {d[e.to] = d[u] + e.dist;p[e.to] = g[u][i];que.push(HeapNode(d[e.to], e.to));}}}}
};
int n, m, k, s, t;
int d1[maxn], d2[maxn];
int p1[maxn], p2[maxn];
Dijkstra di;
void print1(
int x) {
if (x == s) {
printf(
"%d",
1 + s);
return;}Edge& e = di.edges[p1[x]];print1(e.from);
printf(
" %d",
1 + x);
}
void print2(
int x) {
if (x == t) {
printf(
" %d\n",
1 + t);
return;}
printf(
" %d",
1 + x);Edge& e = di.edges[p2[x]];print2(e.from);
}
int main() {
int flag =
0;
while (
scanf(
"%d%d%d", &n, &s, &t) ==
3) {--s, --t;
if (flag)
putchar(
'\n');flag =
1;di.init(n);
scanf(
"%d", &m);
for (
int i =
0; i < m; ++i) {
int u, v, c;
scanf(
"%d%d%d", &u, &v, &c);--u, --v;di.add(u, v, c);di.add(v, u, c);}di.dijkstra(s);
memcpy(d1, di.d,
sizeof(d1));
memcpy(p1, di.p,
sizeof(p1));di.dijkstra(t);
memcpy(d2, di.d,
sizeof(d2));
memcpy(p2, di.p,
sizeof(p2));
int ans = d1[t], sto = -
1, tto = -
1;
scanf(
"%d", &k);
for (
int i =
0; i < k; ++i) {
int u, v, c;
scanf(
"%d%d%d", &u, &v, &c);--u, --v;
if (d1[u] + c + d2[v] < ans) {ans = d1[u] + c + d2[v];sto = u;tto = v;}
if (d1[v] + c + d2[u] < ans) {ans = d1[v] + c + d2[u];sto = v;tto = u;}}
if (-
1 == sto) {print1(t);
printf(
"\n");
printf(
"Ticket Not Used\n");}
else {print1(sto);print2(tto);
printf(
"%d\n", sto +
1);}
printf(
"%d\n", ans);}
return 0;
}
總結
以上是生活随笔為你收集整理的Uva 11374 - Airport Express（枚举+最短路）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
