1. 首页
2. 最短路
3. 本页

ZOJ 2750 Idiomatic Phrases Game（最短路）

将每个字符串的前后四位取出，如果A串的后面四位跟B串的前面四位相等，说明A可以通往B，然后以此建图，直接跑最短路就可以了

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int MAXN = 10000;

#define typec int
//const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大
bool vis[MAXN];
int pre[MAXN];
int cost [1050][1050];
int lowcost[1050];

void Dijkstra(int n,int beg)
{
    for(int i=0; i<n; i++)
    {
        lowcost[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0; j<n; j++)
    {
        int k=-1;
        int Min=INF;
        for(int i=0; i<n; i++)
            if(!vis[i]&&lowcost[i]<Min)
            {
                Min=lowcost[i];
                k=i;
            }
        if(k==-1)
        break;
        vis[k]=true;
        for(int i=0; i<n; i++)
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
            {
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
    }


}

struct node
{
    string qian,hou;
    int w;
}a[1050];

char tmp1[5],tmp2[5];

int main()
{

    int n;
    while(cin>>n&&n!=0)
    {
        string tmp;
        for(int i=0;i<n;++i)
        {
            cin>>a[i].w>>tmp;
            for(int j=0;j<4;++j)
            {
                tmp1[j]=tmp[j];
                tmp2[j]=tmp[tmp.size()-(4-j)];
            }
            tmp1[4]='';
            tmp2[4]='';
           // cout<<tmp1<<" "<<tmp2<<endl;
           a[i].qian=tmp1;
           a[i].hou=tmp2;
           //cout<<a[i].qian<<endl;
        }
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(i==j)
                {
                    cost[i][j]=0;
                }
                else
                    cost[i][j]=INF;
            }
        }
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(i==j)
                    continue;
                if(a[i].hou==a[j].qian)
                {
                    cost[i][j]=a[i].w;
                    //cout<<i<<" "<<j<<" "<<a[i].w<<endl;
                }

            }

        }
        Dijkstra(n,0);

        if(lowcost[n-1]==INF)
        {
            cout<<"-1"<<endl;
        }
        else
        {
            cout<<lowcost[n-1]<<endl;
        }


    }



    return 0;
}