文章

2

粉丝

0

获赞

9

访问

521

头像
最短路径 题解:
P1286 上海交通大学机试题
发布于2025年3月6日 11:52
阅读数 264

在找不到问题了,有没有好心人帮忙看看?crying

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 110, mod = 1e5;
int g[N][N];
LL d[N];
bool st[N];
int pow2[N], p[N];
int n, m;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void dijkstra() {
    // 初始化
    memset(d, 0x3f, sizeof d);
    d[0] = 0;
    // n 次循环
    for (int k = 0; k < n; k ++ ) {

        int minv = 0, mind = 0x3f3f3f3f;
        for (int i = 0; i < n; i ++ ) {
            if (!st[i] && d[i] < mind) {
                mind = d[i];
                minv = i;
            }
        }
        
        st[minv] = true;
        
        for (int i = 0; i < n; i ++ ) {
            if (!st[i]) {
                d[i] = min(d[i], d[minv] + g[minv][i]);
            }
        }
        
    }
    
}

int main() {
    
    pow2[0] = 1;
    for (int i = 1; i < 510; i ++ ) pow2[i] = (LL) 2 * pow2[i - 1...
登录查看完整内容


登录后发布评论

2 条评论
快乐小土狗
2025年3月7日 23:28

for (int i = 1; i < 510; i ++ ) pow2[i] = (LL) 2 * pow2[i - 1] % mod;
这里越界了,pow2定义的大小只有110

赞(1)

戴戴砺山河 : 回复 快乐小土狗: 谢谢,终于好了!

2025年3月8日 10:17