P2910

AnnaQ · 2024-03-12 21:26:34 · 个人记录

思路

为啥都用 floyd 和 dijkstra ？我就用的 spfa 。

SPFA ，是 Bellman-Ford 的优化版本，这是 板子题的传送门 ，在这里我就不细说了，给一个 SPFA 的模版代码。

//开始SPFA
void spfa()
{
    for(int i = 1;i <= n;i++)
    {
        dis[i] = 2147483647;//dis数组，是存储从s点到i点的最短路的
        vis[i] = false;//vis数组，是用来存储目前i号点在不在队列里的
    }
   //先把s号点入队
    q.push(s);
    vis[s] = true;
    dis[s] = 0;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = false;
     //出队列
        for(int i = head[x];i;i = e[i].next)//枚举边
        {
            int y = e[i].to;
            if(dis[y] > dis[x] + e[i].dis)//如果比目前从s到y的最短路还有，就更新最短路
            {
                dis[y] = dis[x] + e[i].dis;
                if(!vis[y])//如果y号点目前不在队列里就入队
                {
                    vis[y] = true;//标记一下，代表y号点目前在队列里
                    q.push(y);//入队
                }
            }
        }
    }
}

这道题的AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10010],d,dis[110],ans;
bool vis[110];
struct edge
{
    int to,w;
};
vector<edge> v[110];
//以下内容为SPFA模版，仅供参考
void spfa(int f,int t)
{
    queue<int> q;
    q.push(f);
    memset(dis,0x3f,sizeof(dis));
    for(int i = 1;i <= n;i++)
    {
        vis[i] = false;
    }
    dis[f] = 0;
    vis[f] = true;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for(int i = 0;i < v[x].size();i++)
        {
            int y = v[x][i].to;
            if(dis[y] > dis[x] + v[x][i].w)
            {
                dis[y] = dis[x] + v[x][i].w;
                if(!vis[y])
                {
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        cin >> a[i];
    }
  //建图
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin >> d;
            v[i].push_back({j,d});
        }
    }
  //SPFA
    for(int i = 1;i < m;i++)
    {
        spfa(a[i],a[i + 1]);
        ans += dis[a[i + 1]];
    }
  //输出
    cout << ans << endl;
    return 0;
}