dijkstra求最短路（多源版本）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3;
int u[N],v[N];
int dist[N][N];
vector<int>e[N];
bool st[N][N];
typedef pair<int,int> PII;
void dijkstra(int root)
{
    priority_queue<PII, vector<PII>, greater<PII>>heap;
    dist[root][root]=0;
    heap.push({0,root});
    while(heap.size())
    {
        auto k=heap.top();
        heap.pop();
        int ver=k.second;
        int distence=k.first;
        if(st[root][ver]) continue;
        st[root][ver]=1;
        for(int i=0;i<e[ver].size();i++)
        {
            if(dist[root][e[ver][i]]>=distence+dist[ver][e[ver][i]])
            {
                dist[root][e[ver][i]]=distence+dist[ver][e[ver][i]];
                heap.push({dist[root][e[ver][i]],e[ver][i]});
            }
        }
    }
}
void solve()
{
    int n,m;
    cin>>n>>m;
    memset(dist,127,sizeof(dist));
    for(int i=1;i<=m;i++)
    {
        int w;
        cin>>u[i]>>v[i]>>w;
        if(!st[u[i]][v[i]])
        {
            st[u[i]][v[i]]=1;
            st[v[i]][u[i]]=1;
            e[u[i]].push_back(v[i]);
            e[v[i]].push_back(u[i]);
        }
        dist[u[i]][v[i]]=min(dist[u[i]][v[i]],w);
        dist[v[i]][u[i]]=min(dist[v[i]][u[i]],w);
    }
    memset(st,0,sizeof(st));
    for(int i=1;i<=n;i++)
    {
        dijkstra(i);
    }
}
signed main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}