牛客等级之题N1 追债之旅 - N2 Rinne Loves Study（8.6场）

92 阅读 0 评论 61 点赞

我是靠谱客的博主雪白红酒，这篇文章主要介绍牛客等级之题N1 追债之旅 - N2 Rinne Loves Study（8.6场），现在分享给大家，希望可以做个参考。

牛客等级之题N1-A.追债之旅（8.6场）

题目描述

小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？

输入描述

第1行输入三个整数n，m，k，代表城市数量，道路数量和指定天数
第2-m+1行，每行输入三个整数u，v，w，代表起点城市，终点城市和支付费用。（数据保证无重边，自环）
第m+2行输入k个整数，第i个整数ai代表第i天欠债人会挥霍的钱。
数据保证：0<n≤1000，0<m≤10000，0<k≤10，1≤u,v≤n，0<w,ai≤1000

输出描述

输出一行，一个整数，代表小明的行程花费和欠债人挥霍的钱的最小总和，如果小明不能抓住欠债人（即不能在第k天及之前到达城n），则输出-1。

题解：维护天数+dijkstra跑最短路

复制代码

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define endl  'n'
#define inf 0x3f3f3f3f
using namespace std;
const int MAX=20010;
int d[15][MAX]; // 天数+从1到i的距离 
int head[MAX];
int a[MAX]; //k天内欠债人挥霍的钱
int n,m,k,idx;
struct Edge
{
     int next;
     int to;
     int w;
}edge[MAX];
void add(int u,int v,int w)
{
    edge[idx].w = w;
    edge[idx].to = v;
    edge[idx].next = head[u];
    head[u] = idx++;
}
struct node
{
	int u,day,w;
	bool operator <(const node &a)const{
		return w>a.w;
	}
};
void dijkstra(int s)  
{
	d[0][s]=0;
	priority_queue<node>que;	
     que.push(node{s,0,0});
     while(!que.empty())
	{
        node p = que.top(); que.pop();
         if(p.w>d[p.day][p.u]) continue;
         for(int i=head[p.u];~i;i= edge[i].next)
		{
             Edge e=edge[i];
            if(p.day+1<=k&&d[p.day][p.u]+e.w+a[p.day+1]<d[p.day+1][e.to])
			{
                 d[p.day+1][e.to]=d[p.day][p.u]+e.w+a[p.day+1];
                 que.push(node{e.to,p.day+1,d[p.day+1][e.to]});
            }
        }
     }
 }
int main()
{
 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 	memset(d,0x3f3f,sizeof(d));
 	memset(head,-1,sizeof(head));
	cin>>n>>m>>k; 
 	for(int i=0;i<m;i++){
 		int u,v,w;	
 		cin>>u>>v>>w;
 		add(u,v,w);
 		add(v,u,w);//注意是可以双向建边的
 	}
 	for(int i=1;i<=k;i++)cin>>a[i];
 	 dijkstra(1);
    int res=inf;
	for(int i=1;i<=k;i++) res=min(res,d[i][n]);
	if(res>=inf)res=-1;
	cout<<res;
 	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
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define endl  'n'
#define inf 0x3f3f3f3f
using namespace std;
const int MAX=20010;
int d[15][MAX]; // 天数+从1到i的距离 
int head[MAX];
int a[MAX]; //k天内欠债人挥霍的钱
int n,m,k,idx;
struct Edge
{
     int next;
     int to;
     int w;
}edge[MAX];
void add(int u,int v,int w)
{
    edge[idx].w = w;
    edge[idx].to = v;
    edge[idx].next = head[u];
    head[u] = idx++;
}
struct node
{
	int u,day,w;
	bool operator <(const node &a)const{
		return w>a.w;
	}
};
void dijkstra(int s)  
{
	d[0][s]=0;
	priority_queue<node>que;	
     que.push(node{s,0,0});
     while(!que.empty())
	{
        node p = que.top(); que.pop();
         if(p.w>d[p.day][p.u]) continue;
         for(int i=head[p.u];~i;i= edge[i].next)
		{
             Edge e=edge[i];
            if(p.day+1<=k&&d[p.day][p.u]+e.w+a[p.day+1]<d[p.day+1][e.to])
			{
                 d[p.day+1][e.to]=d[p.day][p.u]+e.w+a[p.day+1];
                 que.push(node{e.to,p.day+1,d[p.day+1][e.to]});
            }
        }
     }
 }
int main()
{
 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 	memset(d,0x3f3f,sizeof(d));
 	memset(head,-1,sizeof(head));
	cin>>n>>m>>k; 
 	for(int i=0;i<m;i++){
 		int u,v,w;	
 		cin>>u>>v>>w;
 		add(u,v,w);
 		add(v,u,w);//注意是可以双向建边的
 	}
 	for(int i=1;i<=k;i++)cin>>a[i];
 	 dijkstra(1);
    int res=inf;
	for(int i=1;i<=k;i++) res=min(res,d[i][n]);
	if(res>=inf)res=-1;
	cout<<res;
 	return 0;
}

牛客等级之题N2-A.Rinne Loves Study（8.6场）

题目描述

Rinne 喜欢使用一种奇怪的方法背单词，现在这些单词被放在了一个 n times mn×m 的格子里。由于背单词是一个令人烦躁的事情，所以她决定每天只背同一行或者同一列的单词。她一共会背 T 次单词，为了方便巩固，她现在想知道：对于每个单词，最后一次背是什么时候呢？
她这么可爱当然会算啦！但是她想考考你。

输入描述

第一行三个整数 n,m,T。接下来 T 行，第 i+1 行描述第 i 天干了什么，每行的格式如下： 1 x:说明她在这一天背了第 x
行的单词； 2 y说明她在这一天背了第 y 列的单词。输入的所有量的具体意义请参考「题目描述」。

输出描述

输出一个 $n \times m$ 的矩阵 $a$ ， $a_{i,j}$ 表示第 i 行第 j 列这个单词最后一次被背诵是在第几天。

题解：开两个数组分别记录行和列的最后一次出现的天数，按矩阵输出时比较该行和该列的最大天数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#pragma GCC optimize(2)
#include<bits/stdc++.h> 
using namespace std;
#define ll long long
#define endl "n"
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
   int n,m,t;cin>>n>>m>>t;
   vector<int>r(n+1,0),c(m+1,0);
   int a,b;
   for(int i=0;i<t;i++){
   		cin>>a>>b;
   		if(a==1)r[b]=i+1;
   		else c[b]=i+1;
   }
   for(int i=1;i<=n;i++){
   	for(int j=1;j<=m;j++)
   	cout<<max(r[i],c[j])<<" ";
   	cout<<endl;
   }
   return 0;
}