P1529 [USACO2.4]回家 Bessie Come Home

本文主要是介绍P1529 [USACO2.4]回家 Bessie Come Home，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://www.luogu.com.cn/problem/P1529
小坑：要是无向图直接闭眼双向存边，不用多想

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int inf=0x7fffffff;
struct node
{
    int to,dis,nxt;
}e[maxn];
int n,head[maxn],val,cnt,minn,s;
ll dist[maxn];
bool vis[maxn];
char c1,c2;
void add_edge(int from,int to,int dis)
{
    e[++cnt].to=to;
    e[cnt].dis=dis;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
void dijkstra()
{
    dist[s]=0;
    while(!vis[s])
    {
        vis[s]=1;minn=inf;
        for(int i=head[s];i!=-1;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dist[y]>dist[s]+e[i].dis&&!vis[y])
            {
                dist[y]=dist[s]+e[i].dis;
            }
        }
        for(int i=1;i<=52;i++)
        {
            if(minn>dist[i]&&!vis[i])
            {
                minn=dist[i];
                s=i;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    head[0]=-1;
    for(int i=1;i<=52;i++)
        head[i]=-1,dist[i]=inf;
    for(int i=1;i<=n;i++)
    {
        scanf("%s%s%d",&c1,&c2,&val);
        int x,y;
        if(c1>='A'&&c1<='Z')
            x=int(c1-'A')+1;
        else if(c1>='a'&&c2<='z')
            x=int(c1-'a')+27;
        if(c2>='A'&&c2<='Z')
            y=int(c2-'A')+1;
        else if(c2>='a'&&c2<='z')
            y=int(c2-'a')+27;
        add_edge(x,y,val);
        add_edge(y,x,val);
    }
    s=26;
    dijkstra();
    ll tmp=inf,g;
    for(int i=1;i<=25;i++)
    {
        if(tmp>dist[i])
        {
            tmp=dist[i];
            g=i;
        }
    }
    cout<<char(g-1+'A')<<" "<<tmp<<endl;
    return 0;
}

这篇关于P1529 [USACO2.4]回家 Bessie Come Home的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！