#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 30100
using namespace std;
struct abcd{
	int to,f,next;
}table[M*5];
int head[M],tot;
int n,m,f[M],pos[M],heap[M],top;
void push_up(int x)
{
	int t=pos[x];
	while(t>1&&f[heap[t]]<f[heap[t>>1]])
		swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t>>=1;
}
void insert(int x)
{
	heap[++top]=x;
	pos[x]=top;
	push_up(x);
}
void pop()
{
	heap[1]=heap[top--];
	pos[heap[1]]=1;
	int t=2;
	while(t<=top)
	{
		if(f[heap[t+1]]<f[heap[t]])
			t++;
		if(f[heap[t]]<f[heap[t>>1]])
			swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t<<=1;
		else
			break;
	}
}
void Dijkstra()
{
	int i,j,k;
	memset(f,0x3f,sizeof f);
	f[1]=0;
	for(i=1;i<=n;i++)
		insert(i);
	for(j=1;j<=n;j++)
	{
		k=heap[1];pop();
		for(i=head[k];i;i=table[i].next)
			if(f[table[i].to]>f[k]+table[i].f)
			{
				f[table[i].to]=f[k]+table[i].f;
				push_up(table[i].to);
			}
	}
}
void add(int x,int y,int z)
{
	table[++tot].to=y;
	table[tot].f=z;
	table[tot].next=head[x];
	head[x]=tot;
}
int main()
{
	int i,x,y,z;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	Dijkstra();
	cout<<f[n]<<endl;
}

• Re:此题没有负权边 堆优化Dijkstra能过 挂了的检查一下是不是写挂了 (16) qq2567722641 2019-08-18 16:06:54