Dojp1520 gate jumping problem solution

subject

link

https://deeplearning.org.cn/problem/P1520

Literal description

describe

stay EVE In the game , The universe is divided into many regions , There are an indefinite number of stargates in each area , You can jump to a specific area through the Stargate （ The Stargate is bidirectional ）.

Now you are participating BBE Coalition forces and MLGBD The battle of the alliance , But because the spacecraft was damaged , We need to return to the friendly space station in the rear as soon as possible for maintenance .

Try to write a program , Calculate the shortest time to return to the space station .

To simplify the problem , We agreed that the location of the spacecraft is the area 1, The space station is located in the area N.

Input description

The first 1 That's ok , Two integers N,M, They are the total number of regions and the total number of stargates ;

The first 2…M+1 That's ok , Three integers per row X[i],Y[i],Z[i], They are the two areas connected by the Stargate , And the time it takes to jump ;

Output description

An integer , The shortest time required to return to the space station .

Use case input 1

5 3
1 4 5
4 5 1
1 2 7
Use case output 1

6
Use case input 2

10 11
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 11
1 5 7
6 9 3
Use case output 2

28
Tips

about 80% The data of ,1<N<=10000,1<M<50000;

about 100% The data of ,1<N≤30000,1<M<150000,1≤X[],Y[]≤N,1≤Z[]≤4096;

Code implementation

#include<bits/stdc++.h>
using namespace std;

const int maxn=6e4+10;
const int maxm=3e5+10;
int n,m,cnt;
int head[maxn],dis[maxn];
bool vis[maxn];
struct node{
    
	int v,w,nxt;
}e[maxm];
inline void add(int u,int v,int w){
    
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
inline void Dijkstra(int u){
    
	queue<int>q;
	memset(dis,0x3f,sizeof(dis));
	dis[u]=0;
	vis[u]=true;
	q.push(u);
	while(!q.empty()){
    
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=head[x];i;i=e[i].nxt){
    
			if(dis[e[i].v]>dis[x]+e[i].w){
    
				dis[e[i].v]=dis[x]+e[i].w;
				if(!vis[e[i].v]){
    
					vis[e[i].v]=true;
					q.push(e[i].v);
				}
			}
		}
	}
}
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
    
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	Dijkstra(1);
	printf("%d\n",dis[n]);
	return 0;
}