[题解] USACO回家 Bessie Come Home

思路:可以直接把字母当做数字来做,以'Z'为起点SPFA一遍,然后再从'A'到'Y'寻找最短路,输出.

代码很丑,见谅

#include <bits/stdc++.h>
#define inf 0x7ffffff //宏定义正无穷
using namespace std;
const int MN=1000+10;
struct edge{
    int next,dis,to;//前向星存图
}edge[20000+10];
int head[MN],dis[MN];
int edge_num,n,m;
bool vis[MN];
void add(int u,int v,int w){//存边
    edge[++edge_num].next=head[u],
    edge[edge_num].dis=w,
    edge[edge_num].to=v,
    head[u]=edge_num;
}
void SPFA(){ //SPFA最短路算法(不用讲吧)
    queue<int>Q;
    Q.push((int)'Z'),vis[(int)'Z']=true;
    for(int i=0;i<=150;i++)
        dis[i]=inf;
    dis[(int)'Z']=0;            
    while(!Q.empty()){
        int u=Q.front();
        Q.pop(),vis[u]=false;
        for(int i=head[u];i;i=edge[i].next)
            if(dis[edge[i].to]>dis[u]+edge[i].dis){
                dis[edge[i].to]=dis[u]+edge[i].dis;
                if(!vis[edge[i].to]) Q.push(edge[i].to),
                    vis[edge[i].to]=true;
            }
    }
}
void input(){ //读入
    cin>>m;
    for(int i=1;i<=m;i++){
        char a,b; int c;
        cin>>a>>b>>c;
        add((int)a,(int)b,c),
        add((int)b,(int)a,c);
    }
}
int main(){
    ios::sync_with_stdio(false);// 加速cin,cout
    input(),SPFA();
    char ans='A';
    for(char i='B';i<='Y';i++)// 寻找最短的路径并记录
        if(dis[(int)i]<dis[(int)ans])
            ans=i;
    cout<<ans<<' '<<dis[(int)ans];
    return 0;//愉快地结束
}
Last modification:March 23rd, 2019 at 02:24 pm

Leave a Comment