交通网最短路径长

yishujixiaoxiao

2020-04-27

//
// Created by Arc on 2020/4/26.
//

/*
 * 城市交通线路，单向通行，道路之间可能有不通，每条连同的路之间都有相应的费用
 * 求从起点到终点的最小费用
 *
 * 需要一个a[n][n]数组存放每条路的费用，不连同就为０（给不连同加一个特判吧）
 * f[n]表示点i到终点的最小费用，初始值都设为1000000(求最小费用，那你肯定要找个最大值啊）
 * c[i]存放的是它的下一个的下标（画重点，这种方法真的很常见）
 */

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long f[100],c[100],a[100][100];//底下所有的下标都是从1开始的！！！！attention please!
    int n;//总数
    cin>>n;
    memset(a,0, sizeof(a));
    memset(c,0,sizeof(c));
    for (int i = 1; i <= n; ++i) {//下标是从１开始的所以是<=n
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];

        }
    }
        for (int k = 1; k < n; ++k) {
            f[k]=1000000;

        }

        //这里是算法的主体:逆推
        f[n]=0;
        /*
         * 写的时候是从n-1开始的，然后挨个往后比较
         *(某dl说有点像冒泡排序bubblesort,好像确实有点哈哈哈哈）
         * 就比如　1 2 3 4 5　就是从4开始往后跟5比
         * 然后3开始跟4,5比
         * 这里我把3称为固定点，４和５就是跳跃点（方便说明起见，完全杜撰的！）
         */
        for (int i = n-1; i >= 1; i--) {//写的时候是从n-1开始的，然后挨个往后比较
            for (int j = i+1; j <= n; ++j) {//<=n
                /*解释一下底下这行：
                 * a[i][j]>0　就是刚刚说的那个特判嘛，判断有没有相连
                 * f[j]!=1000000　f[j]是正在比较的那一个跳跃点，它要是为1000000那说明它根本不能到终点啊
                 * f[i]>a[i][j]+f[j]　一开始肯定成立，因为f[i]初始为1000000，到后来的时候，如果它大，那就是要改了呗
                 * f[i]=a[i][j]+f[j];　更该成比较小的值
                 * c[i]=j;把这个位置记录下来
                 *
                 * 所以要赋值，需要满足的条件有：
                 * 1.　i,j两点可以通
                 * 2.　j能连接终点
                 * 3. 固定点的f比原来那个要小
                 */
                if((a[i][j]>0) && (f[j]!=1000000) && (f[i]>a[i][j]+f[j]) ){
                    f[i]=a[i][j]+f[j];
                    c[i]=j;
                }

               // if(i==1 && j==n){
                  //  cout<<"minlong="<<f[1]<<endl;//max
                //}

            }

        }
        //输出
         cout<<"minlong="<<f[1]<<endl;//max
        int x=1;
        while(x!=0){//注意这个条件，x为0的时候就不需要输出了
            cout<<x<<" ";
            x = c[x];

        }




    return 0;

}

给一点点样例

Print in:100 2 5 1  0 0 0 0 0 0 
0 0 12 14 0 0 0 0 
0 0 6 10 4 0 0 0 
0 0 13 12 11 0 0 0 
0 0 0 0 0 3 9 0
0 0 0 0 0 6 5 0
0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0Print out:minlong=191 3 5 8 10

说一下小白在这个代码中的一点点有点尴尬的错误：括号匹配问题．有时换编译器（编辑器）换多了就容易混：它有没有自动补全来着？？中括号还好，大括号就会出现一堆bug，因为中括号小括号它自动补全了以后再往上码它也只是跳过它，但是大括号．．．码一个是一个！

最后一句：我原来这么长时间没有写题解了哈哈哈哈，抓住四月的小尾巴干起来！

最短路径算法