最短路径

①弗洛伊德算法

#include <bits/stdc++.h>
using namespace std;
int n, m;//n城市个数、m道路数

const int MAXV = 105;
//大数结构体
struct bign{
    int d[150], len;
    bign(){
        memset(d, 0, sizeof(d));
        len = 0;
    }
};
//输出大数
void print(bign a){
    int len = min(a.len, 5) - 1;//MOD 100000
    while(len > 0 && a.d[len] == 0) len--;//去除余数前导0
    for(int i = len; i >= 0; i--){
        printf("%d", a.d[i]);
    }
}
//高精度a乘以低精度b
bign mul(bign &a, int b){
    bign c;
    int carry = 0;//进位 
    for(int i = 0; i < a.len; i++){
        int tmp = a.d[i] * b + carry;
        c.d[c.len++] = tmp % 10;//个位作为该位结果 
        carry = tmp / 10;//高位部分作为新的进位 
    }
    while(carry != 0){//和加法不同，乘法的进位可能不止一位，因此用while 
        c.d[c.len++] = carry % 10;
        carry /= 10;
    }
    return c;
}
//比较大数大小
int cmp(bign a, bign b){
    if(a.len != b.len) return a.len > b.len ? 1 : -1;
    for(int i = a.len - 1; i >= 0; i--){
        if(a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
    }
    return 0;
}
//大数加法
bign add(bign &a, bign b){
    int carry = 0;
    bign c;
    for(int i = 0; i < a.len || i < b.len; i++){
        int tmp = a.d[i] + b.d[i] + carry;
        c.d[c.len++] = tmp % 10;
        carry = tmp / 10;
    }
    if(carry) c.d[c.len++] = carry;
    return c;
}
//定义城市结构体
struct City{
    bign dis;
};
bign INF; 
City c[MAXV][MAXV];

void init(){
    INF.len = 500;
    fill(INF.d, INF.d + 500, 9);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j)
                c[i][j].dis = INF;//INF代表不可达
            else {c[i][j].dis.len = 1; c[i][j].dis.d[0] = 0; }
        }
    }
}

void Floyd(){
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(cmp(c[i][k].dis, INF) == 0 || cmp(c[k][j].dis, INF) == 0) continue;
                if(cmp(c[i][j].dis, INF) == 0 || cmp(add(c[i][k].dis, c[k][j].dis), c[i][j].dis) == -1){
                    c[i][j].dis = add(c[i][k].dis, c[k][j].dis);
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    init();
    bign k;
    k.d[0] = k.len = 1;
    for(int i = 0; i < m; i++){
        int c1, c2;
        scanf("%d %d", &c1, &c2);
        if(cmp(c[c1][c2].dis, INF) != 0){ k = mul(k, 2); continue; }
        c[c1][c2].dis = c[c2][c1].dis = k;   
        k = mul(k, 2);
    }   
    Floyd();//弗洛伊德算法入口
    //输出0号城市到其他城市的最短路
    for(int i = 1; i < n; i++){
        if(cmp(c[0][i].dis, INF) == 0) printf("-1"); //如果无法到达，输出-1
        else print(c[0][i].dis);
        printf("\n"); 
    }
    return 0;
}