[POJ 1062] 昂贵的聘礼【Dijkstra】

• 2018-01-03
• 0
• 0

Problem:

 Time Limit: 1000MS Memory Limit: 10000K

Description

Input

Output

Sample Input

```1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
```

Sample Output

`5250`

Source

Solution:

##说句题外话，难得在 POJ 上碰到一道中文题，而且又是一道很好的图论题。##

Code: O(n3) [192K, 16MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int M, N, ans;

struct Edge{
int np, val;
Edge *nxt;
};

struct Graph{
Edge *V[105], E[10105];
int L[105], tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, int w){
E[++tope].np = v, E[tope].val = w;
E[tope].nxt = V[u], V[u] = &E[tope];
}
} G;

bool tried[105];
int cost[105];
bool vis[105];

inline int Dijkstra(){
memset(cost, 0x3f, sizeof(cost)), cost[0] = 0;
memset(vis, 0, sizeof(vis));
for(register int i = 0; i <= N; i++){
int mincost = 101;  // Use an empty number as the beginning of the comparation
for(register int j = 0; j <= N; j++)
if(!vis[j] && G.L[j] - G.L[0] <= M && cost[j] < cost[mincost]) mincost = j;
vis[mincost] = 1;  // Find a object with minimum cost
if(mincost == 1) return cost[1];  // The explorer finds out the amount of dowry
for(register Edge *ne = G.V[mincost]; ne; ne = ne->nxt)
if(G.L[ne->np] >= G.L[0] && G.L[ne->np] - G.L[0] <= M)
cost[ne->np] = min(cost[ne->np], cost[mincost] + ne->val);  // Update the cost
}
return 0x3f3f3f3f;
}

int main(){
while(scanf("%d%d", &M, &N) != EOF){
G.clear();
for(register int i = 1; i <= N; i++){
int P, X, T;
scanf("%d%d%d", &P, &G.L[i], &X);
for(register int j = 1; j <= X; j++){
scanf("%d%d", &T, &P);
G.addedge(T, i, P);  // Use surrenal to lower the price
}
}
memset(tried, 0, sizeof(tried)), ans = 0x3f3f3f3f;
for(register int i = 1; i <= N; i++){  // Try to pretend as each level of the owners
if(tried[G.L[i]] || abs(G.L[i] - G.L[1]) > M) continue;
tried[G.L[0] = G.L[i]] = 1;
ans = min(ans, Dijkstra());
}
printf("%d\n", ans);
}
return 0;
}
```

评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai