最短路径
最短路径
https://www.nowcoder.com/practice/a29d0b5eb46b4b90bfa22aa98cf5ff17?tpId=40&tqId=21438&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking
①弗洛伊德算法
#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; }
计算机历年考研复试上机题 文章被收录于专栏
计算机历年考研复试上机题目题解