牛客等級(jí)之題N1-A.追債之旅(8.6場(chǎng))

題目描述

小明現(xiàn)在要追討一筆債務(wù)，已知有n座城市，每個(gè)城市都有編號(hào)，城市與城市之間存在道路相連(每條道路都是雙向的)，經(jīng)過任意一條道路需要支付費(fèi)用。小明一開始位于編號(hào)為1的城市，欠債人位于編號(hào)為n的城市。小明每次從一個(gè)城市到達(dá)另一個(gè)城市需要耗時(shí)1天，而欠債人每天都會(huì)揮霍一定的錢，等到第k天后(即第k+1天)他就會(huì)離開城n并再也找不到了。小明必須要在他離開前抓到他(最開始為第0天)，同時(shí)希望自己的行程花費(fèi)和欠債人揮霍的錢的總和最小，你能幫他計(jì)算一下最小總和嗎？

輸入描述

第1行輸入三個(gè)整數(shù)n，m，k，代表城市數(shù)量，道路數(shù)量和指定天數(shù)

第2-m+1行，每行輸入三個(gè)整數(shù)u，v，w，代表起點(diǎn)城市，終點(diǎn)城市和支付費(fèi)用。(數(shù)據(jù)保證無重邊，自環(huán))

第m+2行輸入k個(gè)整數(shù)，第i個(gè)整數(shù)ai代表第i天欠債人會(huì)揮霍的錢。

數(shù)據(jù)保證：0

輸出描述

輸出一行，一個(gè)整數(shù)，代表小明的行程花費(fèi)和欠債人揮霍的錢的最小總和，如果小明不能抓住欠債人(即不能在第k天及之前到達(dá)城n)，則輸出-1。

題解：維護(hù)天數(shù)+dijkstra跑最短路

#pragma GCC optimize(2)

#include

#define ll long long

#define endl '\n'

#define inf 0x3f3f3f3f

using namespace std;

const int MAX=20010;

int d[15][MAX]; // 天數(shù)+從1到i的距離

int head[MAX];

int a[MAX]; //k天內(nèi)欠債人揮霍的錢

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

return w>a.w;

}

};

void dijkstra(int s)

{

d[0][s]=0;

priority_queueque;

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][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

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<

return 0;

}

牛客等級(jí)之題N2-A.Rinne Loves Study(8.6場(chǎng))

題目描述

Rinne 喜歡使用一種奇怪的方法背單詞，現(xiàn)在這些單詞被放在了一個(gè) n \times mn×m 的格子里。由于背單詞是一個(gè)令人煩躁的事情，所以她決定每天只背同一行或者同一列的單詞。她一共會(huì)背 T 次單詞，為了方便鞏固，她現(xiàn)在想知道：對(duì)于每個(gè)單詞，最后一次背是什么時(shí)候呢？

她這么可愛當(dāng)然會(huì)算啦！但是她想考考你。

輸入描述

第一行三個(gè)整數(shù) n,m,T。 接下來 T 行，第 i+1 行描述第 i 天干了什么，每行的格式如下： 1 x:說明她在這一天背了第 x

行的單詞； 2 y說明她在這一天背了第 y 列的單詞。 輸入的所有量的具體意義請(qǐng)參考「題目描述」。

輸出描述

輸出一個(gè) n × m n×mn×m 的矩陣 a aa，a i , j a_{i,j}ai,j?表示第 i 行第 j 列這個(gè)單詞最后一次被背誦是在第幾天。

題解：開兩個(gè)數(shù)組分別記錄行和列的最后一次出現(xiàn)的天數(shù)，按矩陣輸出時(shí)比較該行和該列的最大天數(shù)

#pragma GCC optimize(2)

#include

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;

vectorr(n+1,0),c(m+1,0);

int a,b;

for(int i=0;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<

cout<

}

return 0;

}

總結(jié)

以上是生活随笔為你收集整理的c语言cin n1 n2,牛客等级之题N1 追债之旅 - N2 Rinne Loves Study（8.6场）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。