还记得刚学C++时觉得最毒瘤的东西是什么吗？

题目描述

现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛)。

在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时，两个牧场(可能是字母相同的)之间会有超过一条道路相连。

至少有一个牧场和谷仓之间有道路连接。因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。牧场被标记为a..z和A..Y,在用大写字母表示的牧场中有一只母牛,小写字母中则没有。谷仓的标记是Z,注意没有母牛在谷仓中。

注意m和M不是同一个牧场否则错误上面的意思是说：输入数据中可能会同时存在M,m（郁闷ing)(PS:表郁闷…告诉我set of咋用就不郁闷了…)，比如
M a a m m z

输入输出格式

输入格式

第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。
第 2 ..P+1行: 用空格分开的两个字母和一个整数:
被道路连接牧场的标记和道路的长度(1<=长度<=1000)。

输出格式

单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。

INPUT & OUTPUT’s examples

Input’s eg #1

5
A d 6
B d 3
C e 9
d Z 8
e Z 3

Output’s eg #1

B 11

分析

强制类型转换！！！

把字母当成数字处理不就好了吗。。

以Z为起点，跑一遍SPFA,然后从A到Y输出最短路即可啊。

这里我们用链式前向星存图，不知道链式前向星的看这里。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* consts */
const int inf = 1e9;
const int MAXN = 1e4+10;
/* definitions */
struct Node{
    int next,to;
    int dis;
};
Node node[MAXN];
int dist[MAXN],head[MAXN],cnt,m;
bool visited[MAXN];
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(){
    queue<int>Q;
    Q.push((int)'Z');
    visited[(int)'Z']=true;
    for(int i=0;i<=MAXN;i++)dist[i]=inf;
    dist[(int)'Z']=0;
    int first,tmp;
    while(!Q.empty()){
        first=Q.front();
        Q.pop();
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                if(!visited[node[i].to]){
                    Q.push(node[i].to);
                    visited[node[i].to]=true;
                }
            }
        }
    }
}
inline void init(){
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        char a,b;
        int c;
        cin>>a>>b>>c;
        Add_Edge((int)a,(int)b,c);
        Add_Edge((int)b,(int)a,c);
    }	
}
int main(int argc,char *argv[]){
    init();SPFA();
    char ans='A';
    for(char i='B';i<='Y';i++){
        if(dist[(int)i]<dist[(int)ans])ans=i;
    }
    cout<<ans<<" "<<dist[(int)ans]<<endl;
    return 0;
}

洛谷P1529题解