程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1181 變形課

HDU 1181 變形課

編輯：C++入門知識

HDU 1181 變形課

多種解法，水題。

DFS，BFS，並查集，最短路。

只要B開頭能到M結尾。

我建立的最短路模型，然後SPFA。。花式AC。。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define PI 3.141592654
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,n) for(int i= a;i< n ;i++)
#define debug puts("==fuck==")
#define acfun std::ios::sync_with_stdio(false)

#define SIZE 20+10
using namespace std;

struct lx
{
    int v,len;
    void init(int vv,int ll)
    {
        v=vv,len=ll;
    }
};

vectorg[27];

void SPFA()
{
    int dis[27];
    bool vis[27];
    FOR(i,0,26)
    {
        dis[i]=INF;
        vis[i]=0;
    }
    dis[1]=0,vis[1]=1;
    queueq;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        FOR(j,0,g[u].size())
        {
            int v=g[u][j].v;
            int len=g[u][j].len;
            if(dis[v]>dis[u]+len)
            {
                dis[v]=dis[u]+len;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[12]==INF)
        puts("No.");
    else
        puts("Yes.");
}
int main()
{
    char str[101];
    while(~scanf("%s",str))
    {
        if(str[0]=='0')
        {
            SPFA();
            FOR(i,0,26)
            g[i].clear();
            continue;
        }
        else
        {
            int len=strlen(str)-1;
            lx now;
            now.init(str[len]-'a',1);
            g[str[0]-'a'].push_back(now);
        }
    }
}