A.HDU 2544 最短路
算是最基础的题目了吧.............我采用的是Dijkstra算法.......
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; #define inf 0x3f3f3f3f
int map[][],d[],vis[],n,m; int Dijkstra()
{
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
d[i]=(i==?:inf);
for(int i=;i<=n;i++)
{
int x,minn=inf;
for(int j=;j<=n;j++)
if(!vis[j] && d[j]<minn)
{
minn=d[j];
x=j;
}
vis[x]=;
for(int y=;y<=n;y++)
d[y]=min(d[y],map[x][y]+d[x]);
}
return d[n];
} int main()
{
int i,u,v,w;
while(~scanf("%d%d",&n,&m),n,m)
{
memset(map,inf,sizeof(map));
for(i=;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=w;
}
printf("%d\n",Dijkstra());
}
return ;
}
B.HDU 3790 最短路径问题
......Loading......
C.HDU 3665 Seaside
题意：就是找到海边的最短路~
这道题其实还是很简单的~就是输入麻烦的点.......╮(╯▽╰)╭把输入搞清了就SO EASY~
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int inf=;
int a[][],b[]; int main()
{
int u,v,i,j,n,s,t,k,sum,ll,number,maxx;
while(~scanf("%d",&n))
{
for(i=;i<n;i++)
for(j=;j<n;j++)
a[i][j]=inf;
for(i=;i<n;i++)
a[i][i]=;
for(i=;i<n;i++)
{
scanf("%d%d",&u,&b[i]); //u代表该镇与几个town相连，b[i]代表该镇是否临海~
for(j=;j<u;j++)
{
scanf("%d%d",&number,&ll); //number代表是哪个镇，ll代表u镇与该镇相连的距离
if(a[i][number]>ll)
a[i][number]=a[number][i]=ll;
}
}
for(i=;i<n;i++)
for(j=;j<n;j++)
for(k=j+;k<n;k++)
if(a[j][k]>a[j][i]+a[i][k])
{
a[j][k]=a[j][i]+a[i][k];
a[k][j]=a[j][k];
}
maxx=inf;
for(i=;i<n;i++)
{
if(a[][i]<maxx && b[i]==)
maxx=a[][i];
}
printf("%d\n",maxx);
}
return ;
}
//memory：264KB time：0ms
D.HDU 1869 六度分离
简而言之~是很简单的题~把每个人的关系都弄出来~只要都满足不大于6个人就是YES，反之NO~
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int inf=;
int a[][]; int main()
{
int u,v,w,i,j,n,m,s,t,k;
while(~scanf("%d%d",&n,&m))
{
for(i=;i<n;i++)
for(j=;j<n;j++)
a[i][j]=inf;
for(i=;i<n;i++)
a[i][i]=;
for(i=;i<m;i++)
{
scanf("%d%d",&u,&v);
a[u][v]=a[v][u]=;
}
for(i=;i<n;i++)
for(j=;j<n;j++)
for(k=j+;k<n;k++)
if(a[j][k]>a[j][i]+a[i][k])
{
a[j][k]=a[j][i]+a[i][k];
a[k][j]=a[j][k];
}
w=;
for(i=;i<n;i++)
for(j=i;j<n;j++)
if(a[i][j]>)
{w=-; break;}
if(w==-) printf("No\n");
else
printf("Yes\n");
}
return ;
}
//memory：320KB time：31ms
E.HDU 1874 畅通工程续
是很简单的题~和A极端的像.............但TLE很多次........刚开始百思不得其解........结果后来发现，就是与A题太像了，结果自己就擅自做主把A题的“输入0,0退出”，直接就套到这道题上了.........T T.........让人泪奔的错误啊.......
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int inf=;
int a[][]; int main()
{
int u,v,w,i,j,n,m,s,t,k;
while(~scanf("%d%d",&n,&m))
{
for(i=;i<n;i++)
for(j=;j<n;j++)
a[i][j]=inf;
for(i=;i<n;i++)
a[i][i]=;
for(i=;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(a[u][v]>w)
a[u][v]=a[v][u]=w;
}
for(i=;i<n;i++)
for(j=;j<n;j++)
for(k=j+;k<n;k++)
if(a[j][k]>a[j][i]+a[i][k])
{
a[j][k]=a[j][i]+a[i][k];
a[k][j]=a[j][k];
}
scanf("%d%d",&s,&t);
if(a[s][t]==inf) printf("-1\n");
else
printf("%d\n",a[s][t]);
}
return ;
}
//memory：332KB time：31ms
F.HDU 1317 XYZZY
......Loading......
G.HDU 4360 As long as Binbin loves Sangsang
......Loading......
H.POJ 1847 Tram
......Loading......
I.POJ 1062 昂贵的聘礼
......Loading......