CCF交通规划--SPFA和dist数组

#include<iostream>#include<cmath>#include<cstring>#include<cstdio>#include<vector>#include<map>#include<queue>#include<algorithm>#define inf 0x3f3f3f3f#define ll long longusing namespace std;const int MAXN=10010;struct Edge{    int from,to,dist;};vector<Edge> edges;vector<int> g[MAXN];bool inq[MAXN];int d[MAXN];int n,m;int cost[MAXN];void init(){    for(int i=1;i<=n;i++)        g[i].clear();    edges.clear();}void addeage(int u,int v,int w){    Edge e;    e.from=u;    e.to=v;    e.dist=w;    edges.push_back(e);    int num=edges.size();    g[u].push_back(num-1);}void spfa(){    queue<int> q;    memset(d,inf,sizeof(d));    memset(inq,0,sizeof(inq));    memset(cost,inf,sizeof(cost));    d[1]=0;    inq[1]=1;    q.push(1);    while(!q.empty())    {        int u=q.front();        q.pop();        inq[u]=0;        for(int i=0;i<g[u].size();i++)        {            Edge e=edges[g[u][i]];            if(d[e.to]>d[u]+e.dist)            {                d[e.to]=d[u]+e.dist;                cost[e.to]=e.dist;                if(!inq[e.to])                {                    q.push(e.to);                    inq[e.to]=1;                }            }            else if(d[e.to]==d[u]+e.dist)                cost[e.to]=min(cost[e.to],e.dist);        }    }}int main(){    cin>>n>>m;    init();    for(int i=1;i<=m;i++)    {        int u,v,w;        scanf("%d%d%d",&u,&v,&w);        addeage(u,v,w);        addeage(v,u,w);    }    spfa();    int sum=0;    for(int i=2;i<=n;i++)        sum+=cost[i];    cout<<sum<<endl;    return 0;}
祭坛