无向图的堆优化Dijkstra求最短路

求从1号点到n号点的最短路径

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long int ll;
using namespace std;

struct node{
    int diss,index;
    bool operator <(const node b)const{
        return this->diss > b.diss;
    }
}tmp;

ll n,m,a,b,s[200010],t[200010],d[200010],fuck;
ll v[200010],dis[200010];
ll first[200010],next1[400010],next2[400010],in_last[400010];

priority_queue <node> q;

void chase(ll x,int i){
	if(!first[x]){
		in_last[x] = i;
		return;
	}
	int last = in_last[x];
	if(s[last] == x) next1[last] = i;
	else next2[last] = i;
	in_last[x] = i;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    cin>>n>>m;
    for(int i = 1; i <= m; ++i){
        cin>>s[i]>>t[i]>>d[i];
        if(s[i]==t[i]) {
        	++fuck;
        	--i;
        	--m;
        	continue;
		}
        if(s[i]>t[i]) swap(s[i],t[i]);
        chase(s[i],i),chase(t[i],i);
        if(!first[s[i]]) first[s[i]] = i;
        if(!first[t[i]]) first[t[i]] = i;
    }
    memset(dis,127/3,sizeof(dis));
    dis[1] = 0;
    tmp.diss = 0, tmp.index = 1;
    q.push(tmp);
    while(q.size()){
        tmp = q.top(),q.pop();
        int ind = tmp.index;
        if(v[ind]) continue;
        v[ind] = 1;
        for(int i = first[ind]; i ; i = (ind==s[i])?next1[i]:next2[i]){
            int end = t[i],len = d[i];
            if(end == ind) end = s[i];
            if(dis[ind]+len < dis[end]){
                dis[end] = dis[ind]+len;
                tmp.diss = dis[end];
                tmp.index = end;
                q.push(tmp);
            }
        }
    }
    cout<<dis[n]<<endl;

    return 0;
}