最短路的板子默写

Dj算法

（好像不太会超时）反正我拿它冲锋了
突然发现自己忘干净了
先梳理一下（和topu不同 topu是找到第一个入度=0，遍历出边
最短路是本次循环找到距离最小点遍历出边
1.建立边 用邻接表e[u]push_back(v)
2.dj函数 最短距离din[]=0x3f3f3f3f;0开始
3.d[s]=0;while遍历 for寻找
4.边从1开始 哨兵=0 u=i找到 vis打标 遍历出边
5.主函数调用 cout<<d[target]
==0x3f3f3f3f就是没有找到

#include <bits/stdc++.h>
using namespace std;
struct node
{int v,w;
};
vector<node>e[100];
int d[100];int visited[100];
int n;
int dj(int s)//虚拟max+1
{d[s]=0;for(int i=0;i<=n;i++){d[i]=0x3f3f3f3f;}memset(visited,0,sizeof(visited));int tt=n;int u=0;while(tt--){for(int i=1;i<=n;i++){if(!visited[i] && d[i]<d[u]) u=i;}if(u==0) break;//没找到 不写我觉得一样 visited[u]=1;//必写 for(auto it:e[u]){int v=it.v;int w=it.w;if(!visited[v])//这个必写 d[v]=min(d[v],d[u]+w);}}
}
int main()
{cin>>n;int s,t;for(int i=1;i<=n;i++){e[i].clear();}for(int i=1;i<=n;i++){int uu,vv,ww;cin>>uu>>vv>>ww;e[uu].push_back({vv,ww});//打包 e[vv].push_back({uu,vv});}dj(s);if(d[t]==0x3f3f3f3f) cout<<"no"<<endl;//不可达的思想 else cout<<d[t]<<endl;
}

floyd 暴力但好用

套汇硬币的负边权的超强应用g[i][i]从自己到自己就是套汇
真的是天才的灵机一动惊艳了我好久希望我也能那么厉害

#include <bits/stdc++.h>
using namespace std;
int d[100][100];
int n;
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}
}int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){d[i][j]=0x3f3f3f3f;//初始化 }}for(int i=0;i<n;i++){int uu,vv,ww;int www=log(ww)*(-1);d[uu][vv]=www;d[vv][uu]=www;}floyd(); for(int i=1;i<=n;i++){if(d[i][i]<0){cout<<"套汇成功"<<endl;break;//一个就行 主函数别轻易return 多组数据！！！ }}
}