題目大意就不說(shuō)啦～
直接枚舉新加入的結(jié)點(diǎn)即可。
以下是我的代碼：
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int kMaxn = 507;
const int kInf = 0x7f7f7f7f;
struct Edge
{
int v, w;
};
int f, n, r[107];
int cnt, first[kMaxn], next[ kMaxn * 40 ];
Edge e[ kMaxn * 40 ];
int ans,value,d[107][kMaxn], near[kMaxn];
void Clear ()
{
cnt=-1;
memset ( first, -1, sizeof ( first ) );
}
void AddEdge ( int u, int v, int w )
{
cnt++;
e[cnt].v = v;
e[cnt].w = w;
next[cnt] = first[u];
first[u] = cnt;
}
void Input ()
{
scanf ( "%d%d", &f, &n );
for ( int i = 1; i <= f; i++ )
scanf ( "%d", &r[i] );
//printf ( "%d\n", r[1] );
getchar ();
Clear ();
string in;
while ( getline ( cin, in ) && !in.empty() )
{
int u, v, w;
istringstream ( in ) >> u >> v >> w;
//printf ( "%d %d %d\n", u, v, w );
AddEdge ( u, v, w );
AddEdge ( v, u, w );
}
}
void SPFA ( int start, int *dist )
{
deque<int> q;
bool inq[kMaxn];
memset ( inq, false, sizeof ( inq ) );
//memset ( dist, 0x7f, sizeof ( dist ) );
for ( int i = 1; i <= n; i++ )
dist[i] = kInf;
dist[start] = 0;
q.push_back( start );
while ( !q.empty() )
{
int u = q.front(); q.pop_front();
inq[u] = false;
for ( int i = first[u]; i != -1; i = next[i] )
{
int v = e[i].v;
if ( dist[v] > dist[u] + e[i].w )
{
dist[v] = dist[u] + e[i].w;
if ( !inq[v] )
{
if ( !q.empty() && dist[v] < dist[q.front()] )
q.push_front( v );
else
q.push_back( v );
inq[v] = true;
}
}
}
}
}
void Solve ()
{
for ( int i = 1; i <= f; i++ )
SPFA ( r[i], d[i] );
//for ( int i = 1; i <= f; i++ )
//{
//for ( int j = 1; j <= n; j++)
//printf ( "%d ", d[i][j] );
//puts ( "" );
//}
memset ( near, 0x7f, sizeof ( near ) );
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= f; j++ )
near[i] = min ( near[i], d[j][i] );
value = kInf;
for ( int i = 1; i <= n; i++ )
{
SPFA ( i, d[f+1] );
int t = 0;
for ( int j = 1; j <= n; j++ )
t = max ( t, min ( near[j], d[f+1][j] ) );
if ( value > t)
{
ans = i;
value = t;
}
}
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen ( "data.in", "r", stdin );
#endif
int T;
bool first_case = true;
scanf ( "%d", &T );
while ( T-- )
{
Input ();
Solve ();
if ( first_case )
first_case = false;
else
puts ( "" );
printf ( "%d\n", ans );
}
return 0;
}
posted on 2011-09-08 00:08
lee1r 閱讀(609)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論