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 ) ) ;
  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  ] ) ;
 }
}