ccf_数据中心spfa
ccf数据中心spfa
我也是第一次考ccf,之前不会算法,考试的时候看这个题,思路就是求各个点到root的所有路径中最小的权值(每条路径最小的权值为这条路径所有边中的最大边值),这个题是最短路径的一个变形,最为一个小渣渣的我,只会spaf这一个算法,下面就是详细代码
#include<iostream>
#include<vector>
#include<string.h>
#include<queue>
#define N 100000
using namespace std;
typedef struct node{
int e,l;
}node;
void spfa();
int Max = 1<<30;
queue<int> q;
vector<node> G[N];
int n,m,root;
bool vis[N];
int ans[N];
int main()
{
cin>>n>>m>>root;
int e1,e2,l;
node e;
for(int i = 0;i<m;i++)
{
cin>>e1>>e2>>l;
e.e = e2;
e.l = l;
G[e1].push_back(e);
e.e = e1;
G[e2].push_back(e);
}
spfa();
l = 0;
for(int i = 1;i<n+1;i++)
{
if(l<ans[i])
l = ans[i];
}
cout<<l;
}
void spfa()
{
for(int i = 0;i<n+1;i++)
{
ans[i] = Max;
}
memset(vis,0,N);
int front,k = 0;
for(int i = 0;i<G[root].size();i++)
{
q.push(G[root][i].e);
ans[G[root][i].e] = G[root][i].l;
vis[G[root][i].e] = 1;
}
while(!q.empty())
{
front = q.front();
q.pop();
vis[front] = 0;
int e,l,b;
for(int i = 0;i<G[front].size();i++)
{
l = G[front][i].l;
e = G[front][i].e;
if(l<ans[front])
b = ans[front];
else b = l;
if(b<ans[e])
{
ans[e] = b;
if(vis[e]==0)
{
vis[e] = 1;
q.push(e);
}
}
}
}
}
运行时间有点长,要是有简单方法大家一起交流进步,因为这次考试分太低了,哈哈,来年再刷,而且这个题考试的时候没有过,而我现在用同样的思路测试就过了。