dijkstra 80tps!
查看原帖
dijkstra 80tps!
774588
Sqrt49楼主2024/4/17 15:55

哪个大佬教教我(QWQ)~

#include<bits/stdc++.h>
using namespace std;
  
struct Edge
{
    int v;
    int w;
    friend bool operator < (Edge a, Edge b)
    {
        return a.w < b.w;
    }
}now, tmp, et, t1, t2;
int n, m, o, t, dis[500001], vis[500001];
int const inf = 0x3f3f3f;
vector<Edge> es[500001];
  
void dijkstra(int s)
{
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    now.v = s;
    now.w = 0;
    priority_queue<Edge> q;
    q.push(now);
    while(!q.empty())
    {
        now = q.top();
        q.pop();
        if(vis[now.v == 1])
        {
            continue;
        }
        vis[now.v] = 1;
        int len = es[now.v].size();
        for(int i = 0; i < len; i++)
        {
            tmp = es[now.v][i];
            if(dis[now.v] + tmp.w < dis[tmp.v])
            {
                dis[tmp.v] = dis[now.v] + tmp.w;
                et.v = tmp.v;
                et.w = dis[tmp.v];
                q.push(et);
            }
        }
    }
}
  
int main()
{
    cin >> n >> m >> o >> t;
    for(int i = 1; i <= n; i++)
    {
        es[i].clear();
    }
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        t1.v = v;
        t1.w = w;
        t2.v = u;
        t2.w = w;
        es[u].push_back(t1);
        es[v].push_back(t2);
    }
    dijkstra(o); 
    cout << dis[t] << endl;
    return 0;
}
2024/4/17 15:55
加载中...