Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: