题目来源

#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,s[200010],t[200010],d[200010];
ll v[200010],dis[200010];
ll first[200010],next[400010],in_last[400010];

priority_queue <node> q;

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];
		next[in_last[s[i]]] = i;
		in_last[s[i]] = i;
		if(!first[s[i]]) first[s[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 = next[i]){
			int end = t[i],len = d[i];
			if(dis[ind]+len < dis[t[i]]){
				dis[t[i]] = dis[ind]+len;
				tmp.diss = dis[t[i]];
				tmp.index = end;
				q.push(tmp);
			}
		}
	}
	cout<<dis[n]<<endl;
	
	
	return 0;
}

就两个测试点，全WA了......