POJ 1062 昂贵的聘礼 (Dijkstra算法)
程序员文章站
2022-06-04 08:10:06
...
解析:一道最短路径题,解决这道题需要弄清楚两点。
1.如何构造出图来。
2.以及如何贪心选取。
对于第一点:如下图。
至于第二点:选取区间m, 在区间中做Dijkstra
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;
int dis[maxn], e[maxn][maxn], tempe[maxn][maxn];
bool visit[maxn];
void solve(int n){
fill(dis, dis + maxn, INF);
memset(visit, false, sizeof(visit));
dis[0] = 0;
for(int i = 0; i < n; ++i){
int u = -1, minn = INF;
for(int j = 0; j <= n; ++j)
if(visit[j] == false && dis[j] < minn){
minn = dis[j];
u = j;
}
if(u == -1) break;
visit[u] = true;
for(int v = 0; v <= n; ++v){
if(dis[v] > dis[u] + e[u][v] && visit[v] == false){
dis[v] = dis[u] + e[u][v];
}
}
}
}
int main(){
int n, m;
int level[maxn];
while(~scanf("%d%d", &m, &n)){
fill(tempe[0], tempe[0] + maxn*maxn, INF);
for(int i = 1; i <= n; ++i){
int x;
scanf("%d%d%d", &tempe[0][i], &level[i], &x);
while(x--){
int t, p;
scanf("%d%d", &t, &p);
tempe[t][i] = p;
}
}
int l = level[1];
int r = l + m;
int left = level[1] - m > 0 ? level[1] - m : 0 , right = left + m;
int k = left , ans = INF ;
while(k <= level[1]){
fill(e[0], e[0] + maxn*maxn, INF);
for(int i = 0; i <= n; ++i){
if(i == 0 || level[i] >= left && level[i] <= right){
for(int j = 0; j <= n; ++j)
e[i][j] = tempe[i][j];
}
}
left++, right++;
solve(n);
ans = min(dis[1], ans);
++k;
}
printf("%d\n", ans);
}
return 0;
}