RT。

样例输入：

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

正确输出：

83

我的输出：

960051511

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+5;
struct node{
    int v,w;
    node(int vv,int ww){
        v=vv;
        w=ww;
    }
    bool operator<(const node &x)const{
        return w<x.w;
    }
};
int n,m;
int dis[maxn];
bool cnt[maxn];
vector<node> G[maxn];
void dijkstra(int s){
    memset(dis,0x3f,sizeof (dis));
    dis[s]=0;
    priority_queue<node> q;
    q.push(node(s,0));
    while(!q.empty()){
        node now=q.top();
        q.pop();
        if(dis[now.v]<now.w) continue;
        for(auto i:G[now.v]){
            if(dis[i.v]<dis[now.v]+i.w){
                dis[i.v]=dis[now.v]+i.w;
                q.push(node(i.v,dis[i.v]));
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back(node(v,w));
        G[v+n].push_back(node(u+n,w));
    }
    dijkstra(1);
    dijkstra(1+n);
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=dis[i]+dis[i+n];
    }
    cout<<sum<<endl;
    return 0;
}

请求julao们指点迷津