CCF-CSP题解 201609-4 交通规划

最小最短路径树。
\(dis[j]==dis[i]+w(i,j)\)时，从\(w(i,j')\)和\(w(i,j)\)考虑。——从0分到100分。
#include <bits/stdc++.h>

const int maxn = 10000;

const int maxm = 100000;

using namespace std;

int to[maxm * 2 + 10];

int w[maxm * 2 + 10];

int nex[maxm * 2 + 10];

int head[maxn + 10], cnt = 0;

void addEdge(int a, int b, int c)

{

    to[cnt] = b; w[cnt] = c;

    nex[cnt] = head[a]; head[a] = cnt++;

    to[cnt] = a; w[cnt] = c;

    nex[cnt] = head[b]; head[b] = cnt++;

}

int edgeVis[maxm + 10];

int dotVis[maxn + 10];

int dis[maxn + 10];

int edgePre[maxn + 10];

void spfa()

{

    memset(edgeVis, 0, sizeof(edgeVis));

    memset(dotVis, 0, sizeof(dotVis));

    memset(dis, 0x3f, sizeof(dis));

    memset(edgePre, -1, sizeof(edgePre));

    queue<int> q;

    dis[1] = 0;

    q.push(1);

    dotVis[1] = 1;

    while (!q.empty())

    {

        int x = q.front(); q.pop();

        dotVis[x] = 0;

        for (int i = head[x]; i != -1; i = nex[i])

        {

            int l = to[i];

            if (dis[l] > dis[x] + w[i])

            {

                dis[l] = dis[x] + w[i];

                if (edgePre[l] != -1)

                    edgeVis[edgePre[l]] = 0;

                edgePre[l] = i / 2;

                edgeVis[edgePre[l]] = 1;

                if (!dotVis[l])

                {

                    q.push(l);

                    dotVis[l] = 1;

                }

            }

            else if (dis[l] == dis[x] + w[i])

            {

                if (w[edgePre[l] * 2] > w[i])

                {

                    edgeVis[edgePre[l]] = 0;

                    edgePre[l] = i / 2;

                    edgeVis[edgePre[l]] = 1;

                }

            }

        }

    }

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

    memset(head, -1, sizeof(head));

    for (int i = 1, a, b, c; i <= m; i++)

    {

        scanf("%d%d%d", &a, &b, &c);

        addEdge(a, b, c);

    }

    spfa();

    int ans = 0;

    for (int i = 0; i <= cnt - 1; i += 2)

    {

        if (edgeVis[i / 2])

        {

            ans += w[i];

        }

    }

    printf("%d\n", ans);

    return 0;

}
巴特西

CCF-CSP题解 201609-4 交通规划

最新文章

热门文章
