#include <iostream>
#include <vector>
using namespace std;
vector <int> v[5001];
int e[5001][5001],max_l;
bool visit[5001];
void dfs(int current,int target,int l)
{
if(current==target)
{
if(l<max_l)
{
max_l=l;
}
return;
}
for(int i=0;i<v[current].size();++i)
{
if(visit[v[current][i]])
{
continue;
}
visit[v[current][i]]=true;
dfs(v[current][i],target,l+e[current][v[current][i]]);
visit[v[current][i]]=false;
}
}
int main()
{
int n,m,y,o,a,b,x;
while(cin>>n>>m>>y>>o)
{
for(int i=1;i<=n;++i)
{
v[i].clear();
visit[i]=false;
}
while(m--)
{
cin>>a>>b>>x;
v[a].push_back(b);
v[b].push_back(a);
e[a][b]=x;
e[b][a]=x;
}
max_l=1e9;
visit[y]=true;
dfs(y,o,0);
cout<<max_l<<endl;
}
}
不知道為何RE 求解
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector <int> v[5001];
int link[5001][5001];
int magic[5001];
queue <int> q;
int main()
{
int n,m,y,o,a,b,x,s,e;
while(cin>>n>>m>>y>>o)
{
for(int i=1;i<=n;++i)
{
v[i].clear();
}
while(m--)
{
cin>>a>>b>>x;
v[a].push_back(b);
v[b].push_back(a);
link[a][b]=x;
link[b][a]=x;
}
for(int i=1;i<=n;++i)
{
magic[i]=1e9;
}
magic[y]=0;
q.push(y);
while(!q.empty())
{
s=q.front();
q.pop();
if(s==o)
{
continue;
}
for(int i=0;i<v[s].size();++i)
{
e=v[s][i];
if(magic[s]+link[s][e]<magic[e])
{
magic[e]=magic[s]+link[s][e];
q.push(e);
}
}
}
cout<<magic[o]<<endl;
}
}
改用BFS寫 還是一直RE 實在是找不出原因