随笔-141  评论-9  文章-3  trackbacks-0
SPFA, Dijkstra, Floyd 都可以.

注意两点之间有重边, 所以要选择最小的.

/*
ID: lorelei3
TASK: comehome
LANG: C++
*/


#include 
<fstream>
#include 
<queue>

using namespace std;

const int MAX = 256;
const int INF = 999999999;
int map[MAX][MAX];
int dist[MAX];
bool isInQ[MAX],f[MAX];
int N;

inline 
bool relax(int u, int v){
    
int len = dist[u]+map[u][v];
    
if(len<dist[v]){
        dist[v] 
= len;
        
return true;
    }

    
return false;
}


void spfa(){
    queue
<int> Q;
    
int be = 'Z',t=0;

    dist[be]
=0;
    map[be][be]
=0;
    Q.push(be);
    isInQ[be]
=true;
    
while(!Q.empty()){
        
int u = Q.front();
        Q.pop();
        isInQ[u]
=false;
        
for(int v=0; v<MAX; ++v)
            
if(relax(u, v) && !isInQ[v]){
                Q.push(v);
                isInQ[v]
=true;
            }

    }

}


int main(){
    
int i,j,v,ans=INF, loc=0;
    
char ch1,ch2;

    ifstream fin(
"comehome.in");
    ofstream fout(
"comehome.out");

    
for(i=0; i<MAX; ++i){
        
for(j=0; j<MAX; ++j)
            map[i][j]
=INF;
    dist[i] 
= INF;
    }



    fin
>>N;

    
for(i=0; i<N; ++i){
        fin
>>ch1>>ch2>>v;
        
if(v<map[ch1][ch2]){
            map[ch1][ch2]
=v;
            map[ch2][ch1]
=v;
        }

        
if(ch1>='A' && ch1<'Z')
            f[ch1]
=true;
        
if(ch2>='A' && ch2<'Z')
            f[ch2]
=true;
    }

    
    spfa();

    
for(i=0; i<MAX; ++i)
        
if(dist[i]<ans && f[i] ){
            ans 
= dist[i];
            loc
= i;
        }



    fout
<<(char)loc<<' '<<ans<<endl;

    
return 0;
}
posted on 2010-12-10 21:23 小阮 阅读(320) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理