使用注釋掉的string和cin會TLE，使用scanf 和 定 義char類型卻不會
[html]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<string,int> MAP ;
const int maxn = 1060 ;
int edge[ maxn ][ maxn ] ;
const int INF = 1000000000 ;
int used[ maxn ] ;
int dist[ maxn ] ;
int path[ maxn ] ;
void Dijkstra( int v0 , int end1 , int n )
{
int i , j , k , u ;
memset( used , 0 ,sizeof( used ) ) ;
for( i = 1 ; i <= n ; i++ )
{
dist[ i ] = INF ;
}
dist[ v0 ] = 0 ;
for( i = 1 ; i < n ; i++ )
{
int MIN = INF , u = v0 ;
for( j = 1 ; j <= n ; j++ )
{
if( !used[ j ] && dist[ j ] < MIN )
{
MIN = dist[ j ] ;
u = j ;
}
}
used[ u ] = 1 ;
for( k = 1 ; k <= n ; k++ )
{
if( !used[ k ] && edge[ u ][ k ] + dist[ u ] < dist [ k ] )
{
dist[ k ] = edge[ u ][ k ] + dist[ u ] ;
path[ k ] = u ;
}
}
}
if( dist[ end1 ] == INF )
cout << "-1" << endl ;
else
cout << dist[ end1 ] << endl ;
}
int main()
{
int i , j , k ;
int temp ;
int n ;
// string start , destination ;
// string begin , end ;
char start[ maxn ] , destination[ maxn ] ;
char begin[ maxn ] , end[ maxn ] ;
while(~scanf( "%d" , &n ) )
{
if( n == -1 )
break ;
MAP.clear() ;
temp = 0 ;
scanf( "%s%s" , start , destination ) ;
//cin >> start >> destination ;
if( !MAP[ start ] )
{
temp++ ;
MAP[ start ] = temp ;
}
if( !MAP[ destination ] )
{
temp++ ;
MAP[ destination ] = temp ;
}
for( i = 0 ; i <= maxn ; i++)
for( j = 0 ; j <= maxn ; j++ )
if( i == j)
edge[ i ][ j ] = 0 ;
else
edge[ i ][ j ] = INF ;
for( i = 1 ; i <= n ; i++)
{
int num ;
scanf( "%s%s%d" , begin ,end ,&num) ;
//cin >> begin >> end >> num ;
if( !MAP[ begin ] )
{
temp++ ;
MAP[ begin ] = temp ;
}
if( !MAP[ end ] )
{
temp++ ;
MAP[ end ] = temp ;
}
edge[ MAP[ begin ] ][ MAP[ end ] ] = edge[ MAP[ end ] ][ MAP[ begin ] ] = num ;
}
Dijkstra( MAP[ start ] , MAP[ destination ] , MAP.size() ) ;
}
return 0 ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<string,int> MAP ;
const int maxn = 1060 ;
int edge[ maxn ][ maxn ] ;
const int INF = 1000000000 ;
int used[ maxn ] ;
int dist[ maxn ] ;
int path[ maxn ] ;
void Dijkstra( int v0 , int end1 , int n )
{
int i , j , k , u ;
memset( used , 0 ,sizeof( used ) ) ;
for( i = 1 ; i <= n ; i++ )
{
dist[ i ] = INF ;
}
dist[ v0 ] = 0 ;
for( i = 1 ; i < n ; i++ )
{
int MIN = INF , u = v0 ;
for( j = 1 ; j <= n ; j++ )
{
if( !used[ j ] && dist[ j ] < MIN )
{
MIN = dist[ j ] ;
u = j ;
}
}
used[ u ] = 1 ;
for( k = 1 ; k <= n ; k++ )
{
if( !used[ k ] && edge[ u ][ k ] + dist[ u ] < dist [ k ] )
{
dist[ k ] = edge[ u ][ k ] + dist[ u ] ;
path[ k ] = u ;
}
}
}
if( dist[ end1 ] == INF )
cout << "-1" << endl ;
else
cout << dist[ end1 ] << endl ;
}
int main()
{
int i , j , k ;
int temp ;
int n ;
// string start , destination ;
// string begin , end ;
char start[ maxn ] , destination[ maxn ] ;
char begin[ maxn ] , end[ maxn ] ;
while(~scanf( "%d" , &n ) )
{
if( n == -1 )
break ;
MAP.clear() ;
temp = 0 ;
scanf( "%s%s" , start , destination ) ;
//cin >> start >> destination ;
if( !MAP[ start ] )
{
temp++ ;
MAP[ start ] = temp ;
}
if( !MAP[ destination ] )
{
temp++ ;
MAP[ destination ] = temp ;
}
for( i = 0 ; i <= maxn ; i++)
for( j = 0 ; j <= maxn ; j++ )
if( i == j)
edge[ i ][ j ] = 0 ;
else
edge[ i ][ j ] = INF ;
for( i = 1 ; i <= n ; i++)
{
int num ;
scanf( "%s%s%d" , begin ,end ,&num) ;
//cin >> begin >> end >> num ;
if( !MAP[ begin ] )
{
temp++ ;
MAP[ begin ] = temp ;
}
if( !MAP[ end ] )
{
temp++ ;
MAP[ end ] = temp ;
}
edge[ MAP[ begin ] ][ MAP[ end ] ] = edge[ MAP[ end ] ][ MAP[ begin ] ] = num ;
}
Dijkstra( MAP[ start ] , MAP[ destination ] , MAP.size() ) ;
}
return 0 ;
}
