记录编号	474089	评测结果	AAAAAAAAAA
题目名称	交换	最终得分	100
用户昵称	ユッキー	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-11-09 17:00:29	内存使用	0.56 MiB

#include <cstdio>
#include <cstring>
#include <cmath>
#define inf 999999999
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct ss
{
    int u,v,w,next;
    ss(){next=0;}
}E[10500];//边
int dis[150][150];
int head[150];
bool vis[150];
int lv[150];
int ca;//等级
int mon[110];
int n,m;
int cnt=0;
queue<int>Q;
void add(int x,int y,int z)
{
    cnt++;
    E[cnt].u=x;
    E[cnt].v=y;
    E[cnt].w=z;
    E[cnt].next=head[x];
    head[x]=cnt;
}
bool pd(int x,int maxx,int minx)
{
    if(abs(lv[E[x].v]-ca)<=m && abs(lv[E[x].v]-maxx)<=m && abs(lv[E[x].v]-minx)<=m)return true;
    return false;
}
void SPFA(int s)
{
    memset(vis,0,sizeof(vis));
    ca=lv[s];
    int maxx=ca;//交换中的max
    int minx=ca;//交换中的min
    dis[s][s]=mon[s];
    vis[s]=1;
    Q.push(s);
    int i,tmp;
    while(!Q.empty())
    {
        tmp=Q.front();
        Q.pop();
        for(i=head[tmp];i;i=E[i].next)
        {
            if(dis[s][E[i].v]>dis[s][tmp]+E[i].w && pd(i,maxx,minx))
            {
                dis[s][E[i].v]=dis[s][tmp]+E[i].w;
                maxx=max(lv[E[i].v],maxx);
                minx=min(lv[E[i].v],minx);
                if(!vis[E[i].v])
                {
                    Q.push(E[i].v);
                    vis[E[i].v]=1;
                }
            }
        }
    }
}
int main()
{
    int i,j;
    freopen("swap.in","r",stdin);
    freopen("swap.out","w",stdout);
    scanf("%d%d",&m,&n);
    for(i=0;i<=n;i++)for(j=0;j<=n;j++)dis[i][j]=inf;
    for(i=1;i<=n;i++)
    {
        int u,x;
        scanf("%d%d%d",&mon[i],&lv[i],&x);
        for(j=1;j<=x;j++)
        {
            int v,w;
            scanf("%d%d",&v,&w);
            add(v,i,w);
        }
    }

    for(i=1;i<=n;i++)
        SPFA(i);

    int minn=mon[1];
    for(i=2;i<=n;i++)
        minn=min(minn,dis[i][1]);
    printf("%d",minn);
    return 0;
}