题目连接
AC代码
#include#include #include #include #include #define MAXN 1000#define INF 0x3f3f3f3fint 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());}