Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

附上 POJ 和 ZOJ 的代码吧哈哈

Posted by liuxueyang at 2021-01-27 23:27:28 on Problem 1122
// POJ
// ============
// 1122. FDNY to the Rescue!.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 30, INF = 0x3f3f3f3f;
int g[N][N], dis[N], pre, n, st[N], sa, en, pa[N], psz;
PII fs[N]; 
int fsz;

void Init() {
    memset(st, 0, sizeof st);
}

void dijkstra() {
    memset(dis, INF, sizeof dis);
    dis[sa] = 0;

    for (int i = 0; i < n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j) {
            if (!st[j] && (t == -1 || dis[j] < dis[t])) {
                t = j;
            }
        }
        st[t] = 1;
        for (int j = 1; j <= n; ++j) {
            if (g[t][j] != -1) {
                dis[j] = min(dis[j], dis[t] + g[t][j]);
            }
        }
    }
}

void path(int x) {
    psz = 0;
    while (sa != x) {
        pa[psz++] = x;
        for (int i = 1; i <= n; ++i) {
            if (i == x || g[i][x] == -1) continue;
            if (g[i][x] + dis[i] == dis[x]) {
                x = i;
                break;
            }
        }
    }
    pa[psz] = sa;
    for (int i = 0; i <= psz; ++i) {
        printf("%d", pa[i]);
        if (i != psz) printf("\t");
        else printf("\n");
    }
}

int main()
{
#ifdef _DEBUG
#pragma warning(disable: 4996)
    freopen("in.txt", "r", stdin);
#endif // _DEBUG

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &g[j][i]);
        }
    }
    scanf("%d", &sa);
    int tmp; fsz = 0;
    while (~scanf("%d", &tmp)) {
        fs[fsz++].second = tmp;
    }
    Init();
    dijkstra();
    printf("Org\tDest	Time	Path\n");
    for (int i = 0; i < fsz; ++i) {
        fs[i].first = dis[fs[i].second];
    }
    sort(fs, fs + fsz);
    for (int i = 0; i < fsz; ++i) {
        printf("%d\t%d\t%d\t", fs[i].second, sa, fs[i].first);
        path(fs[i].second);
    }

    return 0;
}

// ============

// ZOJ
// ============
// FDNY to the Rescue!.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <sstream>

using namespace std;

typedef pair<int, int> PII;

const int N = 30, INF = 0x3f3f3f3f;
int g[N][N], dis[N], pre, n, st[N], sa, en, pa[N], psz;
PII fs[N];
int fsz;

void Init() {
    memset(st, 0, sizeof st);
}

void dijkstra() {
    memset(dis, INF, sizeof dis);
    dis[sa] = 0;

    for (int i = 0; i < n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j) {
            if (!st[j] && (t == -1 || dis[j] < dis[t])) {
                t = j;
            }
        }
        st[t] = 1;
        for (int j = 1; j <= n; ++j) {
            if (g[t][j] != -1) {
                dis[j] = min(dis[j], dis[t] + g[t][j]);
            }
        }
    }
}

void path(int x) {
    psz = 0;
    while (sa != x) {
        pa[psz++] = x;
        for (int i = 1; i <= n; ++i) {
            if (i == x || g[i][x] == -1) continue;
            if (g[i][x] + dis[i] == dis[x]) {
                x = i;
                break;
            }
        }
    }
    pa[psz] = sa;
    for (int i = 0; i <= psz; ++i) {
        printf("%d", pa[i]);
        if (i != psz) printf("\t");
        else printf("\n");
    }
}

int main()
{
#ifdef _DEBUG
#pragma warning(disable: 4996)
    freopen("in.txt", "r", stdin);
#endif // _DEBUG

    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%d", &g[j][i]);
            }
        }
        scanf("%d", &sa);
        int tmp; fsz = 0;
        
        string line;
        getline(cin, line);
        stringstream ss(line);
        while (ss >> tmp) {
            fs[fsz++].second = tmp;
        }

        Init();
        dijkstra();
        printf("Org\tDest	Time	Path\n");
        for (int i = 0; i < fsz; ++i) {
            fs[i].first = dis[fs[i].second];
        }
        sort(fs, fs + fsz);
        for (int i = 0; i < fsz; ++i) {
            printf("%d\t%d\t%d\t", fs[i].second, sa, fs[i].first);
            path(fs[i].second);
        }

        if (T) puts("");
    }

    return 0;
}

// ============

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator