2360: 【作】【基础】回家 Bessie Come Home

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：8 解决：7

题目描述

现在是晚餐时间，而母牛们在外面分散的牧场中。

Farmer John 按响了电铃，所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓（在给出的测试数据中，总会有且只有一只最快的母牛）。在挤奶的时候（晚餐前），每只母牛都在她自己的牧场上，一些牧场上可能没有母牛。

每个牧场由一条条道路和一个或多个牧场连接（可能包括自己）。有时，两个牧场（可能是字母相同的）之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此，所有的母牛最后都能到达谷仓，并且母牛总是走最短的路径。当然，母牛能向着任意一方向前进，并且她们以相同的速度前进。牧场被标记为 lns="http://www.w3.org/1998/Math/MathML">�...� 和 lns="http://www.w3.org/1998/Math/MathML">�...�，在用大写字母表示的牧场中有一只母牛，小写字母中则没有。 谷仓的标记是 lns="http://www.w3.org/1998/Math/MathML">�，注意没有母牛在谷仓中。

注意 m 和 M 不是同一个牧场。

输入

第一行一个整数 lns="http://www.w3.org/1998/Math/MathML">�（lns="http://www.w3.org/1998/Math/MathML">1≤�≤104），表示连接牧场（谷仓）的道路的数目。

接下来 lns="http://www.w3.org/1998/Math/MathML">� 行，每行用空格分开的两个字母和一个正整数：被道路连接牧场的标号和道路的长度（道路长度均不超过 lns="http://www.w3.org/1998/Math/MathML">103）。

输出

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

样例输入 复制 

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

样例输出 复制 

B 11

提示


把 52 个牧场映射成节点（a..z→1..26，A..Y→27..51，谷仓 Z→52），从谷仓 Z 跑一遍 Dijkstra，再在带母牛的大写牧场 A..Y 里找距离最小的那个。


#include <bits/stdc++.h>
using namespace std;
/*
1.本题：求每只母牛（大写字母牧场）到谷仓Z的最短路
  定义r[]存储：每个点来自哪个点
  在更新更短路的时候，更新某个点来自的点
2.描述无向图，且要注意读入两个字母和长度，要自己构建邻接矩阵
  牧场标记为a..z(1..26)、A..Y(27..51)，谷仓Z(52)
3.两点之间可能有多条路径（包括字母相同的）
  多条路的情况下，我们保留两点之间的最短路
*/
const int N = 55;
const int INF = 0x3f3f3f3f;
int a[N][N];//邻接矩阵
int d[N];//存储走到每个点的最短路径长度
bool f[N];//存储哪些点是确定求出最短路长度
int n = 52;//总节点数
//把字母转换成节点编号
int id(char c){
    if(c >= 'a' && c <= 'z') return c - 'a' + 1; //a..z -> 1..26
    return c - 'A' + 27; //A..Z -> 27..52
}
int main(){
    int P;
    cin>>P;
    char x,y;
    int len;
    //读入P条道路
    for(int i = 1;i <= P;i++){
        cin>>x>>y>>len;
        int x1 = id(x), y1 = id(y);
        //如果没有读到边，或者边更短
        //多条边的情况下保留最短边
        if(a[x1][y1]==0 || len < a[x1][y1]){
            a[x1][y1] = len;
            a[y1][x1] = len;
        }
    }
    int Z = id('Z');//谷仓是Z
    //dijkstra：从谷仓Z出发求到每个点的最短路
    memset(d,0x3f,sizeof(d));
    d[Z] = 0;//谷仓的最短路径值可以确定
    for(int i = 1;i <= n;i++){
        int mi = -1;
        //求没有确定的点的最小数下标
        for(int j = 1;j <= n;j++){
            if(!f[j] && (mi == -1 || d[j] < d[mi])){
                mi = j;
            }
        }
        //确定该点的路径是最短的
        f[mi] = true;
        //尝试mi可以去的点中，没有确定的点，是否有更短路
        for(int j = 1;j <= n;j++){
            if(!f[j]&&a[mi][j]!=0&&d[mi]+a[mi][j]<d[j]){
                d[j] = d[mi] + a[mi][j];
            }
        }
    }
    //找距离谷仓最近的带母牛的大写牧场（A..Y = 27..51）
    int ans = 0;
    for(int i = 27;i <= 51;i++){
        if(ans == 0 || d[i] < d[ans]){
            ans = i;
        }
    }
    printf("%c %d\n",'A' + ans - 27, d[ans]);
    return 0;
}


#include <bits/stdc++.h>
using namespace std;

struct edge{
    int from, to, len, next;
};

const int MAXEDGE = 20005;
edge a[MAXEDGE];
int k = 0;
int pre[60];    //最多52个点，开大一点
int s;          //起点是Z
const int INF = 0x3f3f3f3f;
int d[60];
bool f[60];

void add(int u,int v,int l){
    k++;
    a[k].from = u;
    a[k].to = v;
    a[k].len = l;
    a[k].next = pre[ u ];
    pre[ u ] = k;
}

void dijkstra(int n){
    memset(d,0x3f,sizeof(d));
    memset(f,0,sizeof(f));
    d[ s ] = 0;
    
    for(int i = 1; i <= n; i++){
        int mi = -1;
        for(int j = 1; j <= 52; j++){
            if(!f[j] && (mi == -1 || d[j] < d[mi])){
                mi = j;
            }
        }
        f[mi] = true;
        for(int j = pre[mi]; j != 0; j = a[j].next){
            int to = a[j].to;
            if(!f[to] && d[mi] + a[j].len < d[to]){
                d[to] = d[mi] + a[j].len;
            }
        }
    }
}

//字母转编号函数
int char2num(char c){
    if(c >= 'A' && c <= 'Z'){
        return c - 'A' + 1;
    }else{
        return c - 'a' + 27;
    }
}

int main(){
    int P;
    cin >> P;
    for(int i = 1; i <= P; i++){
        char ch1,ch2;
        int w;
        cin >> ch1 >> ch2 >> w;
        int u = char2num(ch1);
        int v = char2num(ch2);
        add(u, v, w);
        add(v, u, w); //双向边
    }
    s = char2num('Z'); //起点：谷仓Z
    dijkstra(52); //总节点最多52个
    
    //遍历A~Y（编号1~25）找最小距离
    char ans_char;
    int min_dist = INF;
    for(int c = 1; c <= 25; c++){
        if(d[ c ] < min_dist){
            min_dist = d[ c ];
            ans_char = 'A' + c - 1;
        }
    }
    cout << ans_char << " " << min_dist;
    return 0;
}

思路回顾

  1. 谷仓是Z，以 Z 作为起点跑 SPFA，求所有牧场到 Z 的最短距离
  2. 字母映射成数字编号：大写 A~Z，小写 a~z，一共 52 个点
    • A →1，B→2 … Z→26
    • a→27，b→28 … z→52
  3. 母牛只在大写A~Y（编号 1~25），遍历这 25 个点，找到距离最小的那个
  4. 道路是双向边，add(u,v,w); add(v,u,w); 

#include <bits/stdc++.h>
using namespace std;

struct edge{
    int from,to,len,next;
};

edge a[200010];
int n,e;
int k;
int pre[200010];
int d[200010];
queue<int> q;
bool f[200010];

void add(int u,int v,int l){
    k++;
    a[k].from = u;
    a[k].to = v;
    a[k].len = l;
    a[k].next = pre[ u ];
    pre[ u ] = k;
}

void spfa(int s){
    memset(d,0x3f,sizeof(d));
    d[ s ] = 0;
    q.push(s);
    f[ s ] = true;//入队标记
    while(!q.empty()){
        int h = q.front();
        for(int i = pre[h];i != 0;i = a[i].next){
            int to = a[i].to;
            if(d[h] + a[i].len < d[to]){
                d[to] = d[h] + a[i].len;
                if(!f[to]){
                    q.push(to);
                    f[to] = true;//在队列中
                }
            }
        }
        f[h] = false;//出队标记
        q.pop();
    }
}

//字母转数字编号
int char2num(char c){
    if(c >= 'A' && c <= 'Z'){
        return c - 'A' + 1;
    }else{
        return c - 'a' + 27;
    }
}

int main(){
    int P;
    cin >> P;
    k = 0;
    memset(pre, 0, sizeof pre); //清空邻接表头
    
    for(int i = 1;i <= P;i++){
        char ch1,ch2;
        int w;
        cin >> ch1 >> ch2 >> w;
        int u = char2num(ch1);
        int v = char2num(ch2);
        add(u, v, w);
        add(v, u, w); //双向边
    }
    int start = char2num('Z'); //起点是Z
    spfa(start);
    
    //在A~Y(1~25)找最小距离
    char ans_c;
    int min_dis = 0x3f3f3f3f;
    for(int i = 1; i <= 25; i++){
        if(d[i] < min_dis){
            min_dis = d[i];
            ans_c = 'A' + i - 1;
        }
    }
    cout << ans_c << " " << min_dis;
    return 0;
}


来源/分类

提交提交记录统计露一手!