hdu1546-Idiomatic Phrases Gamehttp

Dijkstra求解最短路，但是题意中规定当某一字符串的首尾字符相同时才能连接，但是使用如下的方法，这个条件就被忽略了（暗含已经判断了）；

题意大致为给定一个整数和一串字符串，当字符串末端的四个字符与另一字符串的首端四个字符相同时，加上前面的字符串，然后找出连接状态的最小值，而且每一个符合条件的字符串的首尾字符必须相同，才能相加；

将题目转换成求解最短路，然后处理一下对于字符串和对应的整数的关系就可以求出来了

[html]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std ;
const int INF = 1000000000 ;
const int maxn = 1005 ;
int edge[ maxn ][ maxn ] ;
int path[ maxn ] ;
int dist[ maxn ] ;
int used[ maxn ] ;
int n ;
int temp[ maxn ] ;
char str[ maxn ][ maxn ] ;

void Dijkstra( int v0 )
{
    int i , j , k ;
    memset( used , 0 , sizeof( used ) ) ;
    for( i = 0 ; i < n ; i++ )
    {
        dist[ i ] = INF ;
    }
    dist[ 0 ] = 0 ;
    for( i = 0 ; i < n ; i++)
    {
        int MIN = INF , u = v0 ;
        for( j = 0 ; j < n ; j++ )
        {
            if( !used[ j ] && dist[ j ] < MIN )
            {
                MIN = dist[ j ] ;
                u = j ;
            }
        }
        used[ u ] = 1;
        for( k = 0 ; k < n ; k++ )
        {
            if( edge[ u ][ k ] != -1 && (edge[ u ][ k ] + dist[ u ] < dist[ k ] ))
            {
                dist[ k ] = dist[ u ] + edge[ u ][ k ] ;
                path[ k ] = u ;
            }
        }
    }
}

int main()
{
    int i , j , k ;
    while( scanf( "%d" , &n ) != EOF && n )
    {
        memset( temp , 0 , sizeof( temp ) ) ;
        memset( str , 0 , sizeof( str ) ) ;
        for( i = 0 ; i < n ; i++ )
            scanf( "%d%s" , &temp[ i ] , str[ i ] ) ;
        memset( edge , -1 ,sizeof( edge ) ) ;
        for( i = 0 ; i < n ; i++ )
        {
            for( j = 0 ; j < n ; j++ )
            {
                if( i == j )
                    continue ;
                int len = strlen( str[ i ] ) ;
                for( k = 0 ; k < 4 ; k++ )
                {
                    if( str[ i ][ len - 4 + k ] != str[ j ][ k ] )
                        break;
                }
                if( k == 4 )
                    edge[ i ][ j ] = temp[ i ] ;
            }
        }
        Dijkstra( 0 ) ;
        if( dist[ n - 1 ] == INF )
            printf( "-1\n" ) ;
        else
            printf( "%d\n" ,dist[ n - 1 ] ) ;
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std ;
const int INF = 1000000000 ;
const int maxn = 1005 ;
int edge[ maxn ][ maxn ] ;
int path[ maxn ] ;
int dist[ maxn ] ;
int used[ maxn ] ;
int n ;
int temp[ maxn ] ;
char str[ maxn ][ maxn ] ;

void Dijkstra( int v0 )
{
int i , j , k ;
memset( used , 0 , sizeof( used ) ) ;
for( i = 0 ; i < n ; i++ )
{
  dist[ i ] = INF ;
}
dist[ 0 ] = 0 ;
for( i = 0 ; i < n ; i++)
{
  int MIN = INF , u = v0 ;
  for( j = 0 ; j < n ; j++ )
  {
   if( !used[ j ] && dist[ j ] < MIN )
   {
    MIN = dist[ j ] ;
    u = j ;
   }
  }
  used[ u ] = 1;
  for( k = 0 ; k < n ; k++ )
  {
   if( edge[ u ][ k ] != -1 && (edge[ u ][ k ] + dist[ u ] < dist[ k ] ))
   {
    dist[ k ] = dist[ u ] + edge[ u ][ k ] ;
    path[ k ] = u ;
   }
  }
}
}

int main()
{
int i , j , k ;
while( scanf( "%d" , &n ) != EOF && n )
{
memset( temp , 0 , sizeof( temp ) ) ;
memset( str , 0 , sizeof( str ) ) ;
补充：软件开发 , C++ ,