這道題純屬是一個裸的SPFA;
建議先把模闆AC之後再做。
隻需要做一些手腳,就是在加邊的時候加一個雙向邊就好。
然後再第一次加點的時候
看不懂模闆的出門左轉度娘。
推薦下面一片講解:
友鍊是以說,直接上代碼。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
struct data{
int v;int next;
int value;
}edge[500010];//臨界連結清單存變
int cnt;
int alist[10010];
void add(int u,int v,int value)
{
edge[++cnt].v=v;
edge[cnt].value=value;
edge[cnt].next=alist[u];
alist[u]=cnt;
return ;
}//加邊
queue<int> q;
bool ins[10010];
int d[10010];
void spfa(int x)//跑一邊SPFA,原理在上面
{
d[x]=0;
q.push(x);
ins[x]=true;
while(!q.empty())
{
int now=q.front();
q.pop();ins[now]=false;
int next=alist[now];
while(next)
{
int v=edge[next].v;
int value=edge[next].value;
if(d[v]>d[now]+value)
{
d[v]=d[now]+value;
if(!ins[v])
{
q.push(v);
ins[v]=true;
}
}
next=edge[next].next;
}
}
return ;
}
int m,n,s,e;
int main()
{
scanf("%d%d%d%d",&m,&n,&s,&e);//輸入
for(int i=1;i<=n;i++)
{
int u,v,value;
scanf("%d%d%d",&u,&v,&value);
add(u,v,value);//加邊
add(v,u,value);//反向邊
}
for(int i=0;i<=m;i++)
d[i]=0x3f3f3f3f;//初始化
spfa(s);//跑SPFA
printf("%d",d[e]);//輸出
return 0;//程式拜拜
}