P3371 题解

· · 个人记录

using cpp

(C) By: Luogu@kevinbzy(355701)

这道题很模板化，用 SPFA 模板就可以 AC。

SPFA 模板：

void spfa(){
    for(int i=1;i<=n;i++){
        d[i]=2147483647;
    }
    queue<int> q;
    q.push(st);
    vis[st]=1;
    d[st]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].v;
            int w=adj[u][i].w;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

在 main() 主函数中调用函数 spfa() 函数就可以实现功能

由于题目中说是 有向图 ，所以要建一个单向图：

cin>>n>>m>>st;
for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    adj[u].push_back(s(v,w));
}

另外，如果题目中说是 无向图 ，那么就要建一个双向图：

cin>>t>>c>>ts>>te;
for(int i=1;i<=c;i++){
    int u,v,w;      
    cin>>u>>v>>w;   
    adj[u].push_back(s(v,w));
    adj[v].push_back(s(u,w));
}

初始化 & 头文件：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct s{
    int v,w;
    s(int v,int w):v(v),w(w){} 
};
vector<s> adj[500005];
int d[10005],vis[10005],m,u,st,n;

输出：

for(int i=1;i<=n;i++){
    cout<<d[i]<<' ';
}

整体代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct s{
    int v,w;
    s(int v,int w):v(v),w(w){} 
};
vector<s> adj[500005];
int d[10005],vis[10005],m,u,st,n;
void spfa(){
    for(int i=1;i<=n;i++){
        d[i]=2147483647;
    }
    queue<int> q;
    q.push(st);
    vis[st]=1;
    d[st]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].v;
            int w=adj[u][i].w;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>st;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back(s(v,w));
    }
    spfa();
    for(int i=1;i<=n;i++){
        cout<<d[i]<<' ';
    }
    return 0;
}