最短路模板

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dp[105][105];
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
		}
	}
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp,0x3f3f3f,sizeof(dp));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int v,u,w;
		cin>>u>>v>>w;
		dp[u][v]=min(dp[u][v],w);
		dp[v][u]=min(dp[v][u],w);
	}
	for(int i=1;i<=n;i++)dp[i][i]=0;
	floyd();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,s,dis[100005];
bool vis[100005];
struct node{
	int v,w;
	bool operator < (const node &b) const 
	{
		return b.w<w;
	}
};
vector<node>e[100005];
priority_queue<node>pq;
void dij(){
    pq.push({s,0});
	while(pq.size()){
		node tt=pq.top();
		pq.pop();
		int u=tt.v;
		if(vis[u]==1)continue;
		vis[u]=1;	
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].v,w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
                if(!vis[v])pq.push({v,dis[v]});
			}
			
		}
	}
}
signed main(){
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m>>s;
    dis[s]=0;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x].push_back({y,z});
	}
	dij();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,s,dis[100005];
bool vis[100005];
struct node{
	int v,w;
	bool operator < (const node &b) const 
	{
		return b.w<w;
	}
};
vector<node>e[100005];
priority_queue<node>pq;
void dij(){
    pq.push({s,0});
	while(pq.size()){
		node tt=pq.top();
		pq.pop();
		int u=tt.v;
		if(vis[u]==1)continue;
		vis[u]=1;	
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].v,w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
                if(!vis[v])pq.push({v,dis[v]});
			}
			
		}
	}
}
signed main(){
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m>>s;
    dis[s]=0;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x].push_back({y,z});
	}
	dij();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,k,dis[100005];
struct node{
	int u,v;
}e[100005];
signed main(){
	
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	dis[1]=1;
	for(int i=2;i<=n;i++)dis[i]=1e18;
	for(int i=1;i<=n;i++){
		cin>>e[i].u>>e[i].v;
	}
	while(1){
		bool flag=0;
		for(int i=1;i<=n;i++){
			int u=e[i].u,v=e[i].v;
			if(dis[v]>dis[u]+1){
				flag=1;
				dis[v]=dis[u]+1;
			}
		}
		if(!flag)break;
	}
	if(dis[k]==1e18){
		cout<<-1;
		return 0;
	}
	cout<<dis[k];
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,m,s;
struct node{
	int v,w;
};
vector<node>e[N];
queue<int>p;
int dis[N];
bool vis[N];
void spfa(){
	for(int i=1;i<=n;++i){
		vis[i]=0;
		dis[i]=1e18;
	}
	dis[s]=0;
	p.push(s);
	vis[s]=1;
	while(!p.empty()){
		int u=p.front();
		p.pop();
		vis[u]=0;
		for(int i=0;i<e[u].size();++i){
			int v=e[u][i].v;
			int w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					vis[v]=1;
					p.push(v);
				}
			}
		} 	
	}
	return ;
}
signed main(){
	cin>>n>>m;s=1;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		z*=-1;
		e[x].push_back({y,z});

	}
	spfa();
	if(dis[n]==1e18){
		cout<<-1;
		return 0;
	}
	cout<<dis[n]*(-1);
	return 0;
}