ZOJ-3088 Easter Holidays 최단로

제목: 같은 그림의 두 가지 경로를 정하고 어느 점에서 다른 점까지의 경로 길이의 왕복 길이의 비례가 가장 큰 상황을 구한다.이 문제의 두 세트의 그림 처리는 코드를 매우 구역질나게 하고, 마지막에는 경로를 출력해야 한다.최우수값을 계산하고 마지막으로 경로를 계산합니다. 다행히 같은 상황에서 사전 순서에 따라 최소 출력을 요구하지 않았습니다.
코드는 다음과 같습니다.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;
int N, M, K;
struct Edge {
    int v, ct, next;
}e[1005], re[1005];
int idx, ridx, head[1005], rhead[1005];

int path[1005];
int dis[1005][1005];
int rdis[1005][1005];
bool vis[1005];

void insert(int a, int b, int ct, Edge e[], int head[], int &idx) {
    ++idx;
    e[idx].v = b, e[idx].ct = ct;
    e[idx].next = head[a];
    head[a] = idx;
}

void spfa(int sta, int dis[], Edge e[], int head[], int fn) {
    if (fn == 1) {
        memset(dis, 0, sizeof (int) * 1005);
    } else {
        memset(dis, 0x3f, sizeof (int) * 1005);
    }
    memset(vis, 0, sizeof (vis));
    queue<int>q;
    dis[sta] = 0;
    vis[sta] = true;
    q.push(sta);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = false;
        for (int i = head[v]; i != -1; i = e[i].next) {
            if (fn == 1) { //    
                if (dis[e[i].v] < dis[v] + e[i].ct) {
                    dis[e[i].v] = dis[v] + e[i].ct;
                    if (!vis[e[i].v]) {
                        q.push(e[i].v);
                        vis[e[i].v] = true;
                    }
                }
            } else {
                if (dis[e[i].v] > dis[v] + e[i].ct) {
                    dis[e[i].v] = dis[v] + e[i].ct;
                    if (!vis[e[i].v]) {
                        q.push(e[i].v);
                        vis[e[i].v] = true;
                    }
                }    
            }
        }
    }
}

void spfa_path(int sta, int dis[], Edge e[], int head[], int fn) {
    if (fn == 1) {
        memset(dis, 0, sizeof (int) * 1005);
    } else {
        memset(dis, 0x3f, sizeof (int) * 1005);
    }
    memset(path, 0xff, sizeof (path));
    memset(vis, 0, sizeof (vis));
    queue<int>q;
    dis[sta] = 0;
    vis[sta] = true;
    q.push(sta);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = false;
        for (int i = head[v]; i != -1; i = e[i].next) {
            if (fn == 1) { //    
                if (dis[e[i].v] < dis[v] + e[i].ct) {
                    dis[e[i].v] = dis[v] + e[i].ct;
                    path[e[i].v] = v;
                    if (!vis[e[i].v]) {
                        q.push(e[i].v);
                        vis[e[i].v] = true;
                    }
                }
            } else {
                if (dis[e[i].v] > dis[v] + e[i].ct) {
                    dis[e[i].v] = dis[v] + e[i].ct;
                    path[e[i].v] = v;
                    if (!vis[e[i].v]) {
                        q.push(e[i].v);
                        vis[e[i].v] = true;
                    }
                }    
            }
        }
    }    
}

void prt(int x, int &first) {
    if (path[x] != -1) {
        prt(path[x], first);    
    } 
    if (first) {
        printf("%d", x);
        first = 0;
    } else {
        printf(" %d", x);    
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        idx = ridx = -1;
        memset(head, 0xff, sizeof (head));
        memset(rhead, 0xff, sizeof (rhead));
        int a, b, c;
        cin >> N >> M >> K;
        // M      
        for (int i = 0; i < M; ++i) {
            scanf("%d %d %d", &a, &b, &c);
            insert(a, b, c, e, head, idx);
        }
        // K     
        for (int i = 0; i < K; ++i) {
            scanf("%d %d %d", &a, &b, &c);
            insert(a, b, c, re, rhead, ridx);
        }
        for (int i = 1; i <= N; ++i) {
            spfa(i, dis[i], e, head, 1);     //     
            spfa(i, rdis[i], re, rhead, 2); //     
        }
        double Max = 0;
        int x, y; 
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (rdis[j][i] != 0) {
                    if (1.0*dis[i][j]/rdis[j][i] > Max) {
                        x = i, y = j;
                        Max = max(1.0*dis[i][j]/rdis[j][i], Max);
                    }
                }
            }
        }
        int first = 1;
        spfa_path(y, rdis[x], re, rhead, 2);
        prt(path[x], first);
        spfa_path(x, dis[x], e, head, 1);
        prt(y, first);
        printf("
%.3f
", Max);
    }
    return 0;    
}