题解 UVA423

Silence_water · 2020-12-20 21:45:51 · 题解

题目传送门

Description

Analyse

首先我们要求每个机器到 1 号机的最短传递时间，所以是一个单源最短路问题，这里我使用的是 SPFA 算法。

Pay attention

• 由于输入可能是 int 类型，也可能是 char 类型的 x，所以我们可以统一当成字符串，然后用 atoi 将不是 x 的字符串转为 int 类型。

• 输入的是半矩阵，所以要存双向边。

Code

#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
const int M=105;
int n,dis[M],ans;
bool vis[M];
vector<pii> e[M];

void clear(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[s]=0,vis[s]=true;
}//全部初始化 

void init()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)//半矩阵的输入 
        {
            char s[6];
            scanf("%s",s);//统一当成字符串处理 
            if(s[0]=='x')continue;//是x就跳过 
            int w=atoi(s);//用atoi进行转换 
            e[i].push_back(make_pair(j,w));
            e[j].push_back(make_pair(i,w));
        }
}

void spfa(int s)
{
    clear(s);
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=0;i<e[u].size();i++)
        {
            int v=e[u][i].first,w=e[u][i].second;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return;
}//spfa板子
int main()
{
    init();
    spfa(1);
    for(int i=2;i<=n;i++)
        ans=max(ans,dis[i]);//找出最长时间 
    printf("%d",ans);
    return 0;
}

谢谢观看！