By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：
  3. 3. 补充：

题目大意：

要找到一个最短路线，不能只有两个城市，起点和终点要是同一个城市

分析：

  • 最小环问题，要求至少有三个点，则最短路线dis[i][j]中，i != j，再加上k就至少3个点了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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

using namespace std;

const int MAXN = 110;
const int INF = 0x3f3f3f3f;
int mp[MAXN][MAXN], dis[MAXN][MAXN];//这里保存一遍原图，因为floyd算法会修改原图，求最小环的时候要原始数据
int pre[MAXN][MAXN], path[MAXN];    //path数组保存最小环
int n, m;
int sizes;
int mincircle;

void init()
{
    memset(mp, INF, sizeof(mp));
    memset(dis, INF, sizeof(dis));
    for(int i = 0; i < MAXN; i++){
        for(int j = 0; j < MAXN; j++){
            pre[i][j] = i;//pre[i][j]表示 i 到 j 最短路径上 j 前面的一个点
        }
    }
}

void floyd()
{
    mincircle = INF;

    for(int k = 1; k <= n; k++){
        //找最小环
        //最小环判定放floyd前面，因为k要在参与最短路更新前，所以最短路径dis[i][j]中不会有k,所以
		//下面这个双层循环里j从i+1开始，所以i≠j,从而有两个城市了，i<k,j<k所以k为最短路外的一点, 从而有三个城市了
        //最短路外的k + 最短路径成环
        for(int i = 1; i < k; i++){
            for(int j = i + 1; j < k; j++){
                //注意下面这三个判断，一开始忘判断了，结果WA了好久
                if(dis[i][j] != INF && mp[j][k] != INF && mp[k][i] != INF
                   && dis[i][j] + mp[i][k] + mp[k][j] < mincircle){
                    mincircle = dis[i][j] + mp[i][k] + mp[k][j];
                    sizes = 0;
                    int p = j;
                    while(p != i){//用迭代法来回溯，因为至少要3个点： i点+j点+k点，所以j != i
                        path[sizes++] = p;
                        p = pre[i][p];
                    }
                    path[sizes++] = i;//最后把i点和k点加上
                    path[sizes++] = k;
                }
            }
        }

        //正常的floyd部分
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dis[i][j] > dis[i][k] + dis[k][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                    pre[i][j] = pre[k][j];
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF){
        init();
        int from, to, cost;
        while(m--){
            scanf("%d%d%d", &from, &to, &cost);
            if(mp[from][to] > cost)
                mp[from][to] = mp[to][from] = dis[from][to] = dis[to][from] = cost;
        }
        floyd();
        if(mincircle == INF)
            printf("No solution.\n");
        else{
            printf("%d", path[0]);
            for(int i = 1; i < sizes; i++)
                printf(" %d",path[i]);//输出格式控制
            printf("\n");
        }
    }
    return 0;
}

补充：

如果要求最小环且最少两个不同城市，则第一个三层for循环改为：

1
2
3
4
for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
//三个城市成的环可能路径比两个城市成的环路径小
Contents
  1. 1. 题目大意：
  2. 2. 分析：
  3. 3. 补充：