POJ1062 昂贵的聘礼

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=110;
const int inf=1e9;
int g[maxn][maxn];
int p[maxn];
int l[maxn];
int x[maxn];
int t[maxn][maxn];
int v[maxn][maxn];
int d[maxn];
int visit[maxn];
int N,M;
void dijkstra (int s) {
    for (int i=1;i<=N+1;i++) {
        d[i]=inf;
        visit[i]=0;
    }
    d[s]=0;
    for (int i=0;i<N+1;i++) {
        int u=-1;
        double Min=inf;
        for (int j=1;j<=N+1;j++) 
            if (!visit[j]&&d[j]<Min) {
                u=j;
                Min=d[j];
            }
        if (u==-1) return;
        visit[u]=1;
        for (int v=1;v<=N+1;v++) 
            if (!visit[v]&&d[u]+g[u][v]<d[v]) 
                d[v]=d[u]+g[u][v];
    }
}
int main () {
    while (scanf("%d%d",&M,&N)==2) {
        for (int i=1;i<=N;i++) {
            scanf("%d%d%d",&p[i],&l[i],&x[i]);
            for (int j=0;j<x[i];j++) 
                scanf("%d%d",&t[i][j],&v[i][j]);
        }
        int ans=inf;
        for (int k=max(0,l[1]-M);k<=l[1];k++) {
            for (int i=1;i<=N+1;i++) 
                for (int j=1;j<=N+1;j++) {
                    if (i==j) g[i][j]=0;
                    else g[i][j]=inf;
                }
            for (int i=1;i<=N;i++) {
                if (l[i]>k+M||l[i]<k) continue;
                g[N+1][i]=p[i];
                for (int j=0;j<x[i];j++) 
                    if (l[t[i][j]]>=k&&l[t[i][j]]<=k+M) 
                        g[t[i][j]][i]=v[i][j];
            }
            dijkstra(N+1); 
            ans=min(ans,d[1]);
        }
        printf("%d
",ans);
    }
    return 0;
}