POJ 1062 昂貴的聘禮

AC代碼

[cpp] 
#include<iostream>  
#include<algorithm>  
#include<cmath>  
#include <cstdio>  
#include <cstring>  
#define MAXN 1000  
#define INF 0x3f3f3f3f  
int lev[MAXN],pri[MAXN],g[MAXN][MAXN],G[MAXN][MAXN],d[MAXN],vis[MAXN]; 
using namespace std; 
int m,n,k,a,b; 
void dijkstra(int u)//一點到其他點的最短路,鄰接矩陣  
{ 
    memset(vis,0,sizeof(vis)); 
    for(int i=1;i<=m;i++)d[i]=(i==u?0:INF); 
    for(int i=1;i<=m;i++) 
    { 
        int x,l=INF; 
        for(int y=1;y<=m;y++)if(!vis[y]&&d[y]<=l)l=d[x=y]; 
        vis[x]=1; 
        for(int y=1;y<=m;y++) 
            d[y]=min(d[y],d[x]+g[x][y]); 
    } 
} 
void sift(int l,int r)//區間篩選，若一條路的兩端的等級不在[l,r]內,則把g[i][j]置為INF  
{ 
    for(int i=1;i<=m;i++) 
       for(int j=1;j<=m;j++) 
       { 
           if(lev[i]>=l&&lev[i]<=r&&lev[j]>=l&&lev[j]<=r)g[i][j]=G[i][j]; 
           else g[i][j]=INF; 
       } 
} 
int pro() 
{ 
    int ans=INF; 
    for(int i=lev[1]-n;i<=lev[1];i++) 
    { 
        sift(i,i+n);//依次掃描區間  
        dijkstra(1); 
        for(int i=1;i<=m;i++) 
        { 
            d[i]+=pri[i]; 
            ans=min(ans,d[i]); 
        } 
    } 
    return ans; 
} 
int main() 
{ 
 
   scanf("%d%d",&n,&m); 
   for(int i=0;i<=m;i++) 
       for(int j=0;j<=m;j++) 
       { 
           G[i][j]=INF; 
           g[i][j]=INF; 
       } 
   for(int i=1;i<=m;i++) 
   { 
       scanf("%d%d%d",&pri[i],&lev[i],&k); 
       for(int j=1;j<=k;j++) 
       { 
           scanf("%d%d",&a,&b); 
           G[i][a]=b; 
       } 
   } 
   printf("%d\n",pro()); 
} 

#include<iostream>
#include<algorithm>
#include<cmath>
#include <cstdio>
#include <cstring>
#define MAXN 1000
#define INF 0x3f3f3f3f
int lev[MAXN],pri[MAXN],g[MAXN][MAXN],G[MAXN][MAXN],d[MAXN],vis[MAXN];
using namespace std;
int m,n,k,a,b;
void dijkstra(int u)//一點到其他點的最短路,鄰接矩陣
{
    memset(vis,0,sizeof(vis));
 for(int i=1;i<=m;i++)d[i]=(i==u?0:INF);
 for(int i=1;i<=m;i++)
 {
  int x,l=INF;
  for(int y=1;y<=m;y++)if(!vis[y]&&d[y]<=l)l=d[x=y];
  vis[x]=1;
  for(int y=1;y<=m;y++)
   d[y]=min(d[y],d[x]+g[x][y]);
 }
}
void sift(int l,int r)//區間篩選，若一條路的兩端的等級不在[l,r]內,則把g[i][j]置為INF
{
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    {
     if(lev[i]>=l&&lev[i]<=r&&lev[j]>=l&&lev[j]<=r)g[i][j]=G[i][j];
     else g[i][j]=INF;
    }
}
int pro()
{
 int ans=INF;
 for(int i=lev[1]-n;i<=lev[1];i++)
 {
  sift(i,i+n);//依次掃描區間
  dijkstra(1);
  for(int i=1;i<=m;i++)
  {
   d[i]+=pri[i];
   ans=min(ans,d[i]);
  }
 }
 return ans;
}
int main()
{

   scanf("%d%d",&n,&m);
   for(int i=0;i<=m;i++)
    for(int j=0;j<=m;j++)
    {
     G[i][j]=INF;
     g[i][j]=INF;
    }
   for(int i=1;i<=m;i++)
   {
       scanf("%d%d%d",&pri[i],&lev[i],&k);
    for(int j=1;j<=k;j++)
    {
           scanf("%d%d",&a,&b);
     G[i][a]=b;
    }
   }
   printf("%d\n",pro());
}