文章

0

粉丝

1

获赞

1

访问

913

头像
Dijkstra
P1696
发布于2022年9月6日 15:17
阅读数 913

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define debug(x) cout << #x << ":" << x << endl

const int N = 1015;
int ns, na, m, k, spot, g[N][N], dist[N], vis[N], path[N], num[N], spotcar[N];
vector<int> pathAns;

int dijkstra(int s, int d)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    memset(path, 0, sizeof(path));
    memset(num, 0, sizeof(num)); // 经过节点个数
    dist[s] = 0;
    num[s] = 1;
    for (int i = 0; i < ns + na; i++)
    {
        int t = -1;
        for (int j = 1; j <= ns + na; j++)
        {
            if (!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        vis[t] = 1;
        for (int j = 1; j <= ns + na; j++)
        {
            if (dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
                num[j] = num[t] + 1;
       ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发