图论入门基础教程

#include
#include
#include
using namespace std;

#define INF 0x3f3f3f3f
int mp[1100][1100];
int gg[11000];
int vis[11000];
int dis[11000];
int m,n;

int dijkstra()
{
int i,j;
memset(dis,0,sizeof(dis));
for(i&＃61;1; i<&＃61;n; i&＃43;&＃43;)//将从每一个点出发所需要的金币看做0到该点所需要的金币数目
dis[i]&＃61;mp[0][i];
for(i&＃61;1; i {
int mina&＃61;INF;
int u,k;
for(j&＃61;1; j<&＃61;n; j&＃43;&＃43;)
{
if(!vis[j] && dis[j] {
mina&＃61;dis[j];
u&＃61;j;
}
}
vis[u]&＃61;1;
for(k&＃61;1; k<&＃61;n; k&＃43;&＃43;)
{
if(!vis[k] && mp[u][k]dis[u]&＃43;mp[u][k])
dis[k]&＃61;dis[u]&＃43;mp[u][k];
}
}
return dis[1];//返回每一个点到酋长处所花费的钱数
}

int main()
{
while(~scanf("%d%d",&m,&n))
{
int i,j,a,b,c,e,r;
for(i&＃61;0; i<&＃61;n; i&＃43;&＃43;)//初始胡为不能相通
for(j&＃61;0; j<&＃61;n; j&＃43;&＃43;)
mp[i][j]&＃61;INF;
for(i&＃61;1; i<&＃61;n; i&＃43;&＃43;)
{
scanf("%d%d%d",&a,&b,&c);
mp[0][i]&＃61;a;//将从每一个点出发所需要的金币看做0到该点所需要的金币数目
gg[i]&＃61;b;
for(j&＃61;1; j<&＃61;c; j&＃43;&＃43;)
{
scanf("%d%d",&e,&r);
mp[e][i]&＃61;r;//单向路径&＃xff0c;且等级e低于i&＃xff0c;低等级通向高等级
}
}
int minn&＃61;INF;
for(i&＃61;1; i<&＃61;n; i&＃43;&＃43;)//枚举每一个人为最低等级
{
int mnn&＃61;gg[i];
memset(vis,0,sizeof(vis));//注意初始化
for(j&＃61;1; j<&＃61;n; j&＃43;&＃43;)//标记等级差距过大&＃xff0c;和等级低于自己的人
{
if(gg[j]m)
vis[j]&＃61;1;
else
vis[j]&＃61;0;
}
int ss&＃61;dijkstra();
minn&＃61;min(minn,ss);
}
printf("%d\n",minn);
}
return 0;
}