最短路默写
有一无负权有向图。求指定两点间的最短路径。
数据范围：所有数据不超过 100
直接最短路板子写上：
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N],dist[N];
int x,y,z,s,t;
bool vis[N];
int Dijkstra(int s,int t){
memset(dist,0x3f,sizeof dist);
dist[s]=0;
for(int i=1;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++) if(!vis[j]&&(t==-1||dist[j]<dist[t])) t=j;
vis[t]=true;
for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
}
return (dist[t]==0x3f3f3f3f?-1:dist[t]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z);
}
cin>>s>>t;
cout<<Dijkstra(s,t)<<'\n';
return 0;
}