第一次提交就WA了，而且在第一次測試點就WA了！瞅了半天，沒看出來哪錯……最后發(fā)現(xiàn)，"No solution"少了一個"."！無語無語……淡定淡定……
看別人用的是Floyed求最小環(huán)，確實很方便！學(xué)習(xí)了！
我用的是枚舉起點終點+Dijkstra的方法。
以下是我的代碼：
#include<iostream>
#include<string.h>
#define maxn 107
#define INF 20000007
using namespace std;
long n,m,ans,num,g[maxn][maxn],tmp[maxn],path[maxn];
long dijkstra(long begin,long end)
{
long min,minp,d[maxn];
bool used[maxn];
for(long i=1;i<=n;i++)
d[i]=(i==begin?0:INF);
memset(used,false,sizeof(used));
memset(tmp,0,sizeof(tmp));
for(long i=1;i<=n;i++)
{
min=INF;minp=0;
for(long j=1;j<=n;j++)
if(!used[j]&&min>d[j])
{
min=d[j];minp=j;
}
used[minp]=true;
for(long j=1;j<=n;j++)
if(!used[j]&&d[j]>min+g[minp][j])
{
d[j]=min+g[minp][j];
tmp[j]=minp;
}
}
return d[end];
}
int main()
{
while(cin>>n>>m && n!=-1)
{
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
g[i][j]=INF;
for(long i=1;i<=m;i++)
{
long u,v,w;
cin>>u>>v>>w;
if(g[u][v]>w)
g[u][v]=g[v][u]=w;
}
// Input
ans=INF;
memset(path,0,sizeof(path));
// Init
for(long i=1;i<=n;i++)
for(long j=i+1;j<=n;j++)
{
long t=g[i][j],now;
g[i][j]=g[j][i]=INF;
now=dijkstra(i,j)+t;
if(ans>now)
{
ans=now;
// Update
num=0;
memset(path,0,sizeof(path));
long r=j;
while(r)
{
num++;
path[num]=r;
r=tmp[r];
}
// Deal path
}
g[i][j]=g[j][i]=t;
}
// Find the shorest path
if(ans>=INF)
cout<<"No solution."<<endl;
else
{
for(long i=num;i>=1;i--)
{
if(i!=num) cout<<" ";
cout<<path[i];
}
cout<<endl;
}
}
return 0;
}
posted on 2010-09-04 21:08
lee1r 閱讀(339)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論