标签：memset int 路径 iu 最短 问题 vis push sizeof
dijkstra模板
void dijkstra(int iu){
memset(d,88,sizeof(d));
memset(vis,0,sizeof(vis));
d[iu]=0;
q.push({iu,0});
while(!q.empty()){
int x=q.top().u;
q.pop();
vis[x]=true;
for(int i=0;i<g[x].size();i++){
int iv=g[x][i].v,iw=g[x][i].w;
if(!vis[iv]&&d[x]+iw<d[iv]){
d[iv]=d[x]+iw;
q.push({iv,d[iv]});
}
}
}
}
floyd模板
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==k||i==j||j==k)continue;
if(dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
dis[j][i]=dis[i][j];
}
}
}
}
}
【USACO】热浪
#include<bits/stdc++.h>
using namespace std;
int n,cnt,m,d[3005],ans,s,e;
bool vis[3005];
struct node{
int u,dist;
};
struct cmp{
bool operator()(node a,node b){
return a.dist>b.dist;
}
};
struct node2{
int v,w;
};
priority_queue<node,vector<node>,cmp> q;
vector<node2> g[3005];
void dijkstra(int iu){
memset(d,88,sizeof(d));
memset(vis,0,sizeof(vis));
d[iu]=0;
q.push({iu,0});
while(!q.empty()){
int x=q.top().u;
q.pop();
vis[x]=true;
for(int i=0;i<g[x].size();i++){
int iv=g[x][i].v,iw=g[x][i].w;
if(!vis[iv]&&d[x]+iw<d[iv]){
d[iv]=d[x]+iw;
q.push({iv,d[iv]});
}
}
}
}
int main(){
cin>>n>>m>>s>>e;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dijkstra(s);
cout<<d[e]<<endl;
return 0;
}
```#include<bits/stdc++.h>
using namespace std;
int n,cnt,m,d[3005],ans,s,e;
bool vis[3005];
struct node{
int u,dist;
};
struct cmp{
bool operator()(node a,node b){
return a.dist>b.dist;
}
};
struct node2{
int v,w;
};
priority_queue<node,vector<node>,cmp> q;
vector<node2> g[3005];
void dijkstra(int iu){
memset(d,88,sizeof(d));
memset(vis,0,sizeof(vis));
d[iu]=0;
q.push({iu,0});
while(!q.empty()){
int x=q.top().u;
q.pop();
vis[x]=true;
for(int i=0;i<g[x].size();i++){
int iv=g[x][i].v,iw=g[x][i].w;
if(!vis[iv]&&d[x]+iw<d[iv]){
d[iv]=d[x]+iw;
q.push({iv,d[iv]});
}
}
}
}
int main(){
cin>>n>>m>>s>>e;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dijkstra(s);
cout<<d[e]<<endl;
return 0;
}
floyd
#include<bits/stdc++.h>
using namespace std;
int n,m,s,e;
int dis[405][405],g[405][405];
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==k||i==j||j==k)continue;
if(dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
dis[j][i]=dis[i][j];
}
}
}
}
}
int main(){
cin>>n>>m>>s>>e;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
dis[x][y]=z;
dis[y][x]=z;
}
floyd();
cout<<dis[s][e]<<endl;
return 0;
}
标签：memset,
int,
路径,
iu,
最短,
问题,
vis,
push,
sizeof
From： https://www.cnblogs.com/jzx1020/p/17606174.html