畅通工程 小记

1.最短路的板子
2.u=0是哨兵 意味着所有都要+1（0开始的话）！！！起点和终点
3.Dj里的d定义n+1个
4.有多条边时更新之后要存到！！！数组里！！！双向
（通过deepseek检查真的可以收获很多）

#include <bits/stdc++.h>
using namespace std;
int visited[205];
int vis[205][205];
int t;
struct node
{int v,w,n;
}e[1005];
int n,m;
int idx=0;int h[205];
void add(int u,int v,int w)
{e[++idx]={v,w,h[u]};h[u]=idx;
}
int dj(int s)
{memset(visited,0,sizeof(visited));vector<int>d(n+1,0x3f3f3f3f);//从0到n n+1个 d[s]=0;int tt=n;while(tt--){int u=0;for(int i=1;i<=n;i++){if(visited[i]) continue;if(d[i]<d[u]) u=i;}if(!u) break;visited[u]=1;for(int i=h[u];i;i=e[i].n){int v=e[i].v;int w=e[i].w;if(visited[v]) continue;d[v]=min(d[v],d[u]+w);}}return d[t+1];
}
int main()
{while(cin>>n>>m){idx=0;memset(h,0,sizeof(h));int tt=m;memset(vis,0,sizeof(vis));while(m--){int uu,vv,ww;cin>>uu>>vv>>ww;//防止有好多条边 int ttt=vis[uu][vv];if(ttt) {ww=min(ww,ttt);vis[uu][vv]=ww;vis[vv][uu]=ww;}add(uu+1,vv+1,ww);add(vv+1,uu+1,ww);}int s;cin>>s>>t;int ans=dj(s+1);cout<<(ans==0x3f3f3f3f?-1:ans)<<endl;}
}