hdu 2112 hdu today - c++编程基础

被这个水题虐了一晚上，就是因为tot没有初始化，初始化为0的时候就是不超时的时候。这个题目其实还是单源点最短路，稍微有点微不足道的难度，那就是这个题目城市的代号不再是简单的数字了，取而代之的是string的类型。其实很好办，你用map处理一下，这个题目立刻就被打回原形了。这个题目我还是用spfa算法进行的处理，因为这个算法真的挺好用的。直接就是模板题。擦，还被这个悲催的tot摆了一道。

下面看代码，不解释直接就是spfa的最基本用法。

[cpp] #include
#include
#include
#include
#include
#include
using namespace std;
map A;
int list[205];
int dist[205];
const int inf=10000000;
struct node{
int start;
int end;
int len;
int next;
};
node edge[20010];
int vis[205];
int tot,n,m,s,t,coun;
void add(int a,int b,int c)
{
tot=tot+1;
edge[tot].start=a;
edge[tot].end=b;
edge[tot].len=c;
edge[tot].next=list[a];
list[a]=tot;
tot=tot+1;
edge[tot].start=b;
edge[tot].end=a;
edge[tot].len=c;
edge[tot].next=list[b];
list[b]=tot;
}
void spfa(int s)
{
int i,now;
queue q;
for(i=1;i<=coun;i++)
dist[i]=inf;
dist[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
now=q.front();
q.pop();
vis[now]=0;
for(i=list[now];i!=-1;i=edge[i].next)
{
int temp=dist[now]+edge[i].len;
if(dist[edge[i].end]>temp)
{
dist[edge[i].end]=temp;
if(vis[edge[i].end]==0)
{
vis[edge[i].end]=1;
q.push(edge[i].end);
}
}
}
}
}
int main()
{
string str1,str2,beg,en;
int i,chang;
while(scanf("%d",&n)!=EOF&&n!=-1)
{
A.clear();
cin>>beg>>en;
memset(list,-1,sizeof(list));
memset(vis,0,sizeof(vis));
A[beg]=1;
A[en]=2;
coun=3;
tot=0;
for(i=1;i<=n;i++)
{
cin>>str1>>str2>>chang;
if(A.find(str1)==A.end())
{
A[str1]=coun++;
}
if(A.find(str2)==A.end())
{
A[str2]=coun++;
}
add(A[str1],A[str2],chang);
}
spfa(A[beg]);
if(dist[A[en]]==inf)
printf("-1\n");
else printf("%d\n",dist[A[en]]);
}
return 0;
}

#include
#include
#include
#include
#include
#include
using namespace std;
map A;
int list[205];
int dist[205];
const int inf=10000000;
struct node{
int start;
int end;
int len;
int next;
};
node edge[20010];
int vis[205];
int tot,n,m,s,t,coun;
void add(int a,int b,int c)
{
tot=tot+1;
edge[tot].start=a;
edge[tot].end=b;
edge[tot].len=c;
edge[tot].next=list[a];
list[a]=tot;
tot=tot+1;
edge[tot].start=b;
edge[tot].end=a;
edge[tot].len=c;
edge[tot].next=list[b];
list[b]=tot;
}
void spfa(int s)
{
int i,now;
queue q;
for(i=1;i<=coun;i++)
dist[i]=inf;
dist[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
now=q.front();
q.pop();
vis[now]=0;
for(i=list[now];i!=-1;i=edge[i].next)
{
int temp=dist[now]+edge[i].len;
if(dist[edge[i].end]>temp)
{
dist[edge[i].end]=temp;
if(vis[edge[i].end]==0)
{
vis[edge[i].end]=1;
q.push(edge[i].end);
}

hdu 2112 hdu today (一)