【习题】【最短路径习题】AcWing 1375.奶牛回家 两种方法

奶牛回家 Question:Aclass="superseo">cWing 1375.奶牛回家 Question Link:acwing.com/problem/content/1377 Algorithm:Floyd

字母均按ASCII码值处理(lan )

Code：

#include
#include
#include
#include
using namespace std;
const int N=128;
vector<char> v;
int g[N][N];
int p;
pair<char,int> ans;
int main()
{
    ans.second=0x3f3f3f3f;
    memset(g,0x3f,sizeof g);
    cin >> p;
    for (int i = 0; i < p; i++)
    {
        char a,b;
        int c;
        cin >> a >> b >> c;
        g[(int)a][(int)b]=min(g[(int)a][(int)b],c);
        g[(int)b][(int)a]=min(g[(int)a][(int)b],c);
        if(a>='A'&&a<'Z') v.push_back(a);
        if(b>='A'&&b<'Z') v.push_back(b);
    }
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                g[i][j] = min(g[i][j],g[i][k] + g[k][j]);
    vector<char>::iterator it=v.begin();
    for(;it!=v.end();it++)
    {
    	if(ans.second>g[(int)*it]['Z']) 
    	{
    		ans.second=g[(int)*it]['Z'];
    		ans.first=*it;
		}
	}
    cout << ans.first << ' ' << ans.second << endl;
}

Algorithm:dijkstra

啊哈哈哈哈，dijkstra算法来喽！
照样还是用 ASCII (Lazy )

Code:

#include
#include
#include
using namespace std;
const int N=128;
int g[N][N];
int dist[N];//从Z:90到其他位置的最短长度
int p;
bool st[N];
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist['Z']=0;
    for (int i = 65; i <= 122; i++)//65：A 122：z
    {
        int t=-1;
        for (int j = 65; j <= 122; j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        }
        st[t]=true;
        for (int j = 65; j <= 122; j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
}
int main()
{
    memset(g,0x3f,sizeof g);
    for (int i = 0; i < N; i++) g[i][i]=0;
    cin >> p;
    for (int i = 0; i < p; i++)
    {
        char a,b;
        int c;
        cin >> a >> b >> c;
        g[(int)a][(int)b]=min(g[(int)a][(int)b],c);
        g[(int)b][(int)a]=min(g[(int)a][(int)b],c);
    }
    dijkstra();
    int ans=0x3f3f3f3f,anshome;
    for (int i = 'A'; i < 'Z'; i++)//直接遍历有牛的棚，对于不存在的棚也无所谓(因为其dist为INF)
    {
        if(ans>dist[i])
        {
            ans=dist[i];
            anshome=i;
        }
    }
    cout << char(anshome) << ' ' << ans << endl;
    return 0;
}