UVA 11374 - 공항 익 스프 레 스 (최 단거리)

제목 링크: 클릭 하여 링크 열기
제목: 어떤 사람 이 출발점 에서 종점 까지 m 개의 경제 역 과 k 개의 상업 역 이 있어 야 상업 역 을 한 번 만 타고 가장 짧 은 시간 을 구 할 수 있다.
사고: 상업 역 이 많아 서 가장 짧 은 길 을 직접 사용 할 수 없 지만 상업 역 을 이용 할 수 있 는 기회 가 한 번 밖 에 없다 는 것 을 알 게 되 었 기 때문에 어느 상업 역 에 직접 앉 으 면 됩 니 다. 그러면 다른 부분 은 가장 짧 은 길 입 니 다. 상업 역 이 a 에서 b, 소비 c 라 고 가정 하면 답 은 d1 [a] + d2 [b] + c, d1 은 출발점 에서 가장 짧 은 길 입 니 다.d2 는 종점 에서 출발 하 는 가장 짧 은 길이 다.
자세 한 참조 코드:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 500 + 10;
int T,n,m,S,d1[maxn], p1[maxn], d2[maxn], p2[maxn], vis[maxn], ok, dist;
struct node {
    int u, val;
    node(int u=0, int val=0):u(u), val(val) {}
    bool operator < (const node& rhs) const {
        return val > rhs.val;
    }
};
void print(int root, int p[], int id, int S) {
    vector<int> ans;
    while(root != S) {
        ans.push_back(root);
        root = p[root];
    }
    ans.push_back(root);
    int len = ans.size();

    if(id == 1) for(int i=len-1;i>=0;i--) {
        if(i != len-1) printf(" ");
        printf("%d",ans[i]);
    }
    else for(int i=0;i<len;i++) {
        if(i != 0) printf(" ");
        printf("%d",ans[i]);
    }
}
vector<node> g[maxn];
void BFS(int haha, int d[], int p[]) {
    priority_queue<node> q;
    q.push(node(haha, 0));
    for(int i=1;i<=n;i++) {
        d[i] = INF;
    }
    d[haha] = 0;
    memset(vis, false, sizeof(vis));
    while(!q.empty()) {
        node u = q.top(); q.pop();
        if(vis[u.u]) continue;
        vis[u.u] = true;
        int len = g[u.u].size();
        for(int i=0;i<len;i++) {
            node v = g[u.u][i];
            if(d[v.u] > d[u.u] + v.val) {
                d[v.u] = d[u.u] + v.val;
                p[v.u] = u.u;
                q.push(node(v.u, d[v.u]));
            }
        }
    }
}
int a,b,c,kase=0;
int main() {
    while(~scanf("%d%d%d",&n,&S,&T)) {
        scanf("%d",&m);
        for(int i=1;i<=n;i++) g[i].clear();
        while(m--) {
            scanf("%d%d%d",&a,&b,&c);
            g[a].push_back(node(b, c));
            g[b].push_back(node(a, c));
        }
        scanf("%d",&m);
        ok = -1;
        BFS(S, d1, p1);
        BFS(T, d2, p2);
        int s = -1,t = -1,ans = d1[T], res = 0;
        for(int i=0;i<m;i++) {
            scanf("%d%d%d",&a,&b,&c);
            int cur = d1[a] + d2[b] + c;
            if(cur < ans) {
                ans = cur;
                s = a; t = b;
            }
            cur = d1[b] + d2[a] + c;
            if(cur < ans) {
                ans = cur;
                s = b; t = a;
            }
        }
        if(kase) printf("
");
        else ++kase;
        if(s > 0) {
            print(s, p1, 1, S); printf(" ");
            print(t, p2, 2, T); printf("
");
            printf("%d
",s);
        }
        else {
            print(T, p1, 1, S); printf("
");
            printf("Ticket Not Used
");
        }
        printf("%d
",ans);
    }
    return 0;
}