POJ - 1062 昂贵的聘礼（Dijkstra）

POJ - 1062 昂贵的聘礼

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e6+10, INF = 1e9;
int g[110][110],dis[N],level[N],st[N];
int n,m;
int dijkstra(int up,int down) 
{
    memset(dis,0x3f,sizeof dis);memset(st,0,sizeof st);dis[0]=0;for(int i=1;i<=n;i++) {
    int t,minn=INF;for(int j=0;j<=n;j++)//注意从0开始if(!st[j]&&minn>dis[j])t=j,minn=dis[j];st[t]=1;for(int j=1;j<=n;j++) if(level[j]>=up&&level[j]<=down) dis[j]=min(dis[j],dis[t]+g[t][j]);}return dis[1];
}
int main() 
{
    cin>>m>>n;memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++) g[i][i]=0;for(int i=1;i<=n;i++) {
    int price,cnt;cin>>price>>level[i]>>cnt;g[0][i]=min(g[0][i],price);while(cnt--){
    int id,cost;cin>>id>>cost;g[id][i]=min(g[id][i],cost);}}int ans=INF;for(int i=level[1]-m;i<=level[1];i++) ans=min(ans,dijkstra(i,i+m));cout<<ans<<endl;return 0; 
}