首页 > 代码库 > 昂贵的聘礼---poj1062（最短路）

昂贵的聘礼---poj1062（最短路）

2024-08-11 12:55:22   219人阅读

题目链接：http://poj.org/problem?id=1062

题意很清楚；

可以虚拟一个起点0，由于存在等级关系，所以可以枚举等级，然后把各种关系建立边，然后计算0到1的距离即可，去最小值即可；

 

技术分享
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <queue>#include <stack>#include <algorithm>#include <map>#include <string>typedef long long LL;#define INF 0x3f3f3f3f#define met(a, b) memset(a, b, sizeof(a))#define N 515using namespace std;int n, m, G[N][N], dist[N], vis[N];struct node{    int p, l, x, T[N], V[N];}a[N];int Dij(int L, int R){    for(int i=0; i<=n; i++)///重新建图；    {        for(int j=0; j<=n; j++)            G[i][j] = INF;        G[i][i] = 0;        dist[i] = INF;    }    for(int i=1; i<=n; i++)    {        G[i][0] = a[i].p;        for(int j=1; j<=a[i].x; j++)        {            int v = a[i].T[j], w = a[i].V[j];            if(a[v].l >= L && a[v].l <= R)                G[i][v] = min(G[i][v], w);        }    }    met(vis, 0);    dist[1] = 0;    for(int i=0; i<=n; i++)    {        int Min = INF, Index = -1;        for(int j=0; j<=n; j++)        {            if(!vis[j] && Min > dist[j])            {                Min = dist[j];                Index = j;            }        }        if(Index == -1)break;        vis[Index] = 1;        for(int j=0; j<=n; j++)        {            if(!vis[j] && dist[j] > dist[Index] + G[Index][j])                dist[j] = dist[Index] + G[Index][j];        }    }    return dist[0];}int main(){    while(scanf("%d %d", &m, &n) != EOF)    {        for(int i=1; i<=n; i++)        {            scanf("%d %d %d", &a[i].p, &a[i].l, &a[i].x);            for(int j=1; j<=a[i].x; j++)                scanf("%d %d", &a[i].T[j], &a[i].V[j]);        }        int ans = INF;        for(int i=a[1].l-m; i<=a[1].l; i++)///寻找等级区间内符合条件的；        {            ans = min(ans, Dij(i, i+m));        }        printf("%d\n", ans);    }    return 0;}
View Code

 

昂贵的聘礼---poj1062（最短路）


联系
我们