#include <stdio.h>
#include <map>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
#define INF 0xfffffff
int n,m;
int
d[205],w[205][205],hp[205],path[205],l[205],totalhp[205],av_hp[205];
bool vis[205];
map<string,int> mp;
string str[205];
int num[205];
void Dj(int s)
{
int i,j;
for(i=0;i<n;i++)
if(w[s][i]!=INF)
{
d[i]=w[s][i],path[i]=s,totalhp[i]=hp[i],l[i]=1,num[i]=1;
}
else
d[i]=INF;
d[s]=0;
l[s]=0;
num[s]=1;
vis[s]=true;
for(j=0;j<n-1;j++)
{
int min=INF,idx=-1;
for(i=0;i<n;i++)
if(!vis[i]&&d[i]<min)
min=d[i],idx=i;
vis[idx]=true;
if(min==INF)
break;
for(i=0;i<n;i++)
if(!vis[i]&&w[idx][i])
{
if(d[idx]+w[idx][i]<d[i])
{
num[i]=num[idx];
d[i]=d[idx]+w[idx][i];
path[i]=idx;
totalhp[i]=totalhp[idx]+hp[i];
l[i]=l[idx]+1;
av_hp[i]=totalhp[i]/l[i];
}
else if(d[idx]+w[idx][i]==d[i])
{
num[i]+=num[idx];
if(totalhp[idx]+hp[i]>totalhp[i]||(totalhp[idx]+hp[i]==totalhp[i]&&l[idx]+1<l[i]))
{
path[i]=idx;
totalhp[i]=totalhp[idx]+hp[i];
l[i]=l[idx]+1;
av_hp[i]=totalhp[i]/l[i];
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
w[i][j]=INF;
char a1[10];
scanf("%s",a1);
mp[a1]=0;
char a[10];
int t;
for(i=1;i<n;i++)
{
scanf("%s",a),scanf("%d",&t);
str[i]=a,mp[a]=i,hp[i]=t;
}
char b[10];
for(i=0;i<m;i++)
{
scanf("%s%s%d",a,b,&t);
int x=mp[a],y=mp[b];
if(t<w[x][y])
w[x][y]=w[y][x]=t;
}
i=mp["ROM"];
Dj(0);
printf("%d %d %d
%d\n",num[i],d[i],totalhp[i],av_hp[i]);
vector<int> v;
j=path[i];
while(j!=0)
v.push_back(j),j=path[j];
i=v.size()-1;
printf("%s->",a1);
for(j=i;j>=0;j--)
printf("%s->",str[v[j]].c_str());
printf("ROM\n");
return 0;
}
这个代码为什么是错的。
这一行改成 printf("%d %d %d
%d\n",num[i],d[i],totalhp[i],totalhp[i]/l[i]); 就对了。
为什么。两者有区别吗
