洛谷P1796 汤姆斯的天堂梦

传送门

题目描述

汤姆斯生活在一个等级为 00 的星球上。那里的环境极其恶劣，每天 1212 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 NN 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。

汤姆斯预先知道了从 00 等级星球去 NN 等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。

输入格式

第一行一个正整数 NN（N \le 100N≤100），接下来的数据可分为 NN 个段落，每段的第一行一个整数 K_iK
i
​
（K_i \le 100K
i
​
≤100），表示等级为 ii 的星球有 K_iK
i
​
个。

接下来的 K_iK
i
​
行中第 jj 行依次表示与等级为 ii，编号为 jj 的星球相连的等级为 i - 1i−1 的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过 10001000）。

每行以 00 结束，每行的航线数 \le 100≤100。

输出格式

输出所需（或所得）费用。正数表示支出，负数表示收益。

输入输出样例

输入 #1复制
3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0
输出 #1复制
-1

说明/提示

对于 100 %100% 的数据，1 \le N \le 1001≤N≤100，1 \le K_i \le 1001≤K
i
​
≤100。

样例解释：

上代码：

#include
#include
#include
#include
#include
#define re register
#define maxn 100001
#define mp make_pair
#define inf 99999999
using namespace std;
typedef pair<int,int> pii;
map<pii,int> m1;
map<int,pii> m2;
int r[maxn],q[maxn],d[maxn];
int head[maxn];
int n,m,num,k;
struct node
{
	int v,nxt,w;
}e[maxn];
inline void add_edge(int x,int y,int z)
{
	e[++num].v=y;
	e[num].w=z;
	e[num].nxt=head[x];
	head[x]=num;
}
inline int read()
{
    char c=getchar();
    int x=0,r=1;
    while(c<'0'||c>'9')
    {
        if(c=='-') r=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x*r;
}
int main()
{
	m=read();
	m1[mp(0,1)]=++n;
	m2[n]=mp(0,1);
	int p,t;
	for(re int i=1;i<=m;i++)
	{
		k=read();
		for(re int j=1;j<=k;j++)
		{
			m1[mp(i,j)]=++n;
			m2[n]=mp(i,j);
			while(1)
			{
				p=read();
				if(!p) break;
				t=read();
				add_edge(m1[mp(i-1,p)],n,t);
				r[n]++;
			}
		}
	}
	q[1]=1;
	int tot=1;
	for(re int i=1;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	for(re int i=1;i<=tot;i++)
	{
		for(re int j=head[q[i]];j;j=e[j].nxt)
		{
			r[e[j].v]--;
			d[e[j].v]=min(d[e[j].v],d[q[i]]+e[j].w);
			if(!r[e[j].v]) q[++tot]=e[j].v;
		}
	}
	int ans=inf;
	for(re int i=n;i;i--)
	if(m2[i].first==m) ans=min(ans,d[i]);
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83