求调！！邻接矩阵存图
查看原帖
求调！！邻接矩阵存图
1321184
wsthtk楼主2024/9/16 15:48

求调

为什么我用邻接表存图答案是对的（下面注释掉的代码），用邻接矩阵就是错的？

#include <bits/stdc++.h>
using namespace std;

int n, m;
int g[1005][1005];
int g_2[1005][1005];
int dis[1005];
bool vis[1005];

void dijkstra(int s, int op)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    int cnt = n;
    while (cnt--)
    {
        int u = 0;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && dis[i] < dis[u])
                u = i;

        vis[u] = 1;
        for (int i = 1; i <= n; i++)
        {
            int v = i, w = (op == 1 ? g[u][v] : g_2[u][v]);
            if (dis[u] + w < dis[v]) // && w!=0x3f3f3f3f)
                dis[v] = dis[u] + w;
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    memset(g_2, 0x3f, sizeof(g_2));
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = w;
        g_2[v][u] = w; // 反图
    }

    dijkstra(1, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        // cout << dis[i] << " ";
        ans += dis[i];
    }
    cout << endl;

    dijkstra(1, 2);
    for (int i = 1; i <= n; i++)
    {
        // cout << dis[i] << " ";
        ans += dis[i];
    }

    cout << ans << endl;
    return 0;
}

// 用邻接表答案是对的
// #include <bits/stdc++.h>
// using namespace std;

// struct edge
// {
//     int v, w;
// };

// // struct node
// // {
// //     int u, dis;
// //     bool operator<(const node &a)const
// //     {
// //         return dis > a.dis;
// //     }
// // };

// int n, m;
// vector<edge> g[1005];
// vector<edge> g_2[1005];
// int dis[1005];
// bool vis[1005];

// void dijkstra(int s, int op)
// {
//     // priority_queue<node> q;
//     memset(dis, 0x3f, sizeof(dis));
//     memset(vis, 0, sizeof(vis));
//     dis[s] = 0;
//     int cnt = n - 1;
//     while (cnt--)
//     {
//         int u = 0;
//         for (int i = 1; i <= n; i++)
//             if (!vis[i] && dis[i] < dis[u])
//                 u = i;

//         vis[u] = 1;
//         for (edge e : (op == 1 ? g[u] : g_2[u]))
//         {
//             int v = e.v, w = e.w;
//             if (!vis[v] && dis[u] + w < dis[v])
//                 dis[v] = dis[u] + w;
//         }
//     }
// }

// int main()
// {
//     cin >> n >> m;
//     while (m--)
//     {
//         int u, v, w;
//         cin >> u >> v >> w;
//         g[u].push_back({v, w});
//         g_2[v].push_back({u, w});
//     }

//     dijkstra(1,1);
//     int ans = 0;
//     for (int i = 1; i <= n; i++)
//     {
// //      cout << dis[i] << " ";
//         ans += dis[i];
//     }
//     cout << endl;
//     dijkstra(1,2);
//     for (int i = 1; i <= n; i++)
//     {
// //      cout << dis[i] << " ";
//         ans += dis[i];
//     }
//     cout << endl;

//     cout << ans << endl;
//     return 0;
// }

测试数据

50 250
41 49 10
13 15 5
50 14 7
27 12 3
18 19 6
34 23 10
29 33 9
20 42 9
10 45 10
17 2 6
36 47 3
12 16 4
35 36 10
50 13 6
39 48 10
18 46 8
10 9 9
31 46 8
12 1 5
36 7 4
32 2 6
38 10 1
40 49 6
30 35 3
48 20 6
20 28 1
43 21 1
12 20 1
15 14 5
35 6 8
34 9 10
20 19 8
43 41 10
33 28 10
23 14 1
8 33 5
39 18 9
41 7 5
22 29 2
27 5 1
24 36 6
50 27 1
49 14 2
21 14 10
26 37 8
43 13 8
8 45 2
7 38 1
36 12 9
19 27 2
37 33 10
39 45 7
41 43 8
12 16 3
22 34 7
23 33 6
44 49 3
44 15 6
12 13 9
13 25 9
27 42 5
13 44 8
27 47 10
25 36 2
38 4 3
10 14 3
11 46 7
13 44 7
1 5 3
1 22 3
17 14 1
19 22 6
46 9 3
22 13 2
19 11 6
30 3 6
26 29 7
29 49 6
29 22 9
25 49 5
38 4 8
17 7 6
13 20 1
26 25 1
44 16 1
44 11 2
7 19 3
12 21 5
42 13 9
35 3 8
4 18 7
20 19 2
41 40 10
14 50 6
3 34 3
33 5 1
4 12 9
38 16 4
12 41 5
25 45 8
34 30 1
11 21 7
3 5 5
44 3 2
27 1 1
35 22 1
32 33 10
19 5 6
47 30 10
37 47 7
42 15 10
7 2 1
31 36 6
21 38 2
44 46 5
9 37 10
49 17 4
13 40 5
16 8 3
7 31 7
33 30 4
14 47 5
22 10 7
46 9 8
11 45 3
37 50 10
1 40 3
18 43 7
39 7 4
47 2 2
45 35 2
12 38 4
23 40 4
34 24 7
5 30 9
20 28 8
32 41 1
37 48 3
19 23 8
28 20 2
41 31 10
35 7 7
42 41 7
48 27 5
48 18 4
4 45 5
3 39 4
7 49 9
8 28 2
26 50 1
37 24 10
49 34 2
9 7 5
33 30 10
18 26 9
10 42 5
27 24 7
27 37 5
27 45 10
36 29 2
40 28 9
14 15 5
20 4 5
31 30 9
1 11 2
29 2 10
30 39 5
32 13 6
23 31 1
33 16 10
29 46 8
50 28 2
36 17 4
36 15 7
25 30 1
34 40 3
43 5 8
47 5 1
49 13 5
21 36 4
2 19 10
39 45 8
3 11 3
22 3 10
17 37 6
25 10 1
6 50 8
50 2 9
38 16 9
45 5 6
45 18 10
9 49 1
29 33 8
18 50 2
35 27 10
42 27 2
13 7 6
20 46 6
46 22 4
1 28 8
30 27 4
15 10 9
45 18 1
9 8 6
36 47 2
49 7 10
27 33 2
22 39 10
47 7 6
34 41 1
27 45 7
5 49 3
42 37 3
45 31 3
2 26 7
50 49 5
37 14 7
42 46 5
6 25 7
34 32 7
29 18 5
26 14 8
30 10 4
4 36 3
9 17 6
36 7 3
23 17 10
29 6 4
27 34 9
9 38 7
29 34 6
32 11 8
14 27 2
39 31 8
10 41 6
22 39 4
46 31 4
24 44 9
8 36 4
36 44 3
8 21 8
22 24 1
30 38 4
22 41 7
41 37 9
41 31 9
33 30 10
36 9 5
43 14 1
20 10 4

out:

818
2024/9/16 15:48