https://www.luogu.org/problemnew/show/P2299
这就是一道裸题,就不讲什么了,需要学习的话去看模板
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define MAXN 2505
struct ctrl{
int to,dis,next;
}edge[400005];
int f[MAXN],num,n,m,first[MAXN];
bool judge[MAXN];
struct cmp{
bool operator () (int a,int b)
{
return f[a]>f[b];
}
};
priority_queue < int , vector < int > , cmp > q ;
void read(int x,int y,int z)
{
edge[++num].to=y;
edge[num].dis=z;
edge[num].next=first[x];
first[x]=num;
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
read(x,y,z);
read(y,x,z);
}
memset(f,0x7f,sizeof(f));
f[1]=0;
judge[1]=true;
q.push(1);
while(!q.empty())
{
int u=q.top();
judge[u]=0;
q.pop();
for(int i=first[u];i!=0;i=edge[i].next)
{
int v=edge[i].to;
if(f[v]>f[u]+edge[i].dis)
{
f[v]=f[u]+edge[i].dis;
if(!judge[v])
{
judge[v]=1;
q.push(v);
}
}
}
}
printf("%d\n",f[n]);
return 0;
}