UVA 11374 Airport Express（枚举+最短路）

枚举每条商业线<a, b>，设d[i]为起始点到每点的最短路，g[i]为终点到每点的最短路，ans便是min{d[a] + t[a, b] + g[b]}。注意下判断是否需要经过商业线。输出也有点坑的，每两组间用空行隔开。。。

#include<iostream>

#include<algorithm>

#include<vector>

#include<string>

#include<queue>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<fstream>

#include<sstream>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define LL long long

#define PB push_back

#define debug puts("**debug**")

using namespace std;

const int maxn = 1000;

const int INF = 10000000;

int n, s, e, m, k, x[maxn], y[maxn], z[maxn], flag;

struct Heap

{

    int d, u;

    bool operator < (const Heap& rhs) const

    {

        return d > rhs.d;

    }

};

struct Edge

{

    int from, to, dist;

};

vector<Edge> edges;

vector<int> G[maxn];

bool done[maxn];

int d[2][maxn], p[2][maxn], path[maxn];

inline void init()

{

    REP(i, n+1) G[i].clear(); edges.clear();

}

void dij(int s, int cur)

{

    priority_queue<Heap> q; q.push((Heap){0, s});

    REP(i, n+1) d[cur][i] = INF; d[cur][s] = 0;

    CLR(done, 0);

    while(!q.empty())

    {

        Heap x = q.top(); q.pop();

        int u = x.u, nc = G[u].size();

        if(done[u]) continue;

        done[u] = 1;

        REP(i, nc)

        {

            Edge& e = edges[G[u][i]];

            if(d[cur][e.to] > d[cur][u] + e.dist)

            {

                d[cur][e.to] = d[cur][u] + e.dist;

                p[cur][e.to] = edges[G[u][i]].from;

                q.push((Heap){d[cur][e.to], e.to});

            }

        }

    }

}

void add(int from, int to, int dist)

{

    edges.PB((Edge){from, to, dist});

    edges.PB((Edge){to, from, dist});

    int nc = edges.size();

    G[from].PB(nc-2);

    G[to].PB(nc-1);

}

void read()

{

    scanf("%d", &m);

    REP(i, m)

    {

        scanf("%d%d%d", &x[i], &y[i], &z[i]);

        add(x[i], y[i], z[i]);

    }

    scanf("%d", &k);

    REP(i, k) scanf("%d%d%d", &x[i], &y[i], &z[i]);

}

void solve()

{

    dij(s, 0);

    dij(e, 1);

    int ans = d[0][e], tot = d[0][e], a, b;

    REP(i, k)

    {

        int tmp = d[0][x[i]] + d[1][y[i]] + z[i];

        if(tmp < ans) ans = tmp, a = x[i], b = y[i];

        tmp = d[0][y[i]] + d[1][x[i]] + z[i];

        if(tmp < ans) ans = tmp, a = y[i], b = x[i];

    }

    if(ans == tot)

    {

        int cnt = 0, u = e; path[cnt++] = e;

        while(u != s) path[cnt++] = p[0][u], u = p[0][u];

        FD(i, cnt-1, 0) printf("%d%c", path[i], i == 0 ? '\n' : ' ');

        puts("Ticket Not Used");

        printf("%d\n", tot);

    }

    else

    {

        int cnt = 0, tmp[maxn], u = a;

        while(u != s) tmp[cnt++] = p[0][u], u = p[0][u];

        REP(i, cnt) path[i] = tmp[cnt-i-1];

        path[cnt] = a, path[++cnt] = b, cnt++;

        u = b;

        while(u != e) path[cnt++] = p[1][u], u = p[1][u];

        REP(i, cnt) printf("%d%c", path[i], i == cnt - 1 ? '\n' : ' ');

        printf("%d\n%d\n", a, ans);

    }

}

int main()

{

    flag = 0;

    while(~scanf("%d%d%d", &n, &s, &e))

    {

        if(flag) puts("");

        flag++;

        init();

        read();

        solve();

    }

    return 0;

}

巴特西

UVA 11374 Airport Express（枚举+最短路）

最新文章

热门文章