用SPFA求出dist的值

对于每条u，v，w的边检查是否dist[u]+w==dist[v]，求出首都到其他城市的最小路径有向图，每个城市可能对应有多条路径，但无一例外的是每个城市对应的路径都是最小值

该有向图为DAG，对其求最小树形图，也就是对每个节点sum+=以v节点为弧头的所有边中的最小权值

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=10005;
#define INF 0x3f3f3f3f

struct edge{
    int u,v,w;
};
vector<edge> edges;
vector<int> G[maxn];
vector<edge> edges_2;
vector<int> G_2[maxn];
int dist[maxn];
int vis[maxn];

void spfa(int s){
    queue<int> q;
    for(int i=1;i<=n;i++){
        dist[i]=INF;
    }
    dist[s]=0;
    q.push(s);
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<G[u].size();i++){
            edge& e=edges[G[u][i]];
            if(dist[u]+e.w<dist[e.v]){
                dist[e.v]=dist[u]+e.w;
                if(vis[e.v]==0){
                    q.push(e.v);
                    vis[e.v]=1;
         ...