题解 P1280 【尼克的任务】
tong_xz
2019-03-03 12:31:59
### 这道题可以用最短路（最长路？）做。
将时间点作为图论的点。
从第P分钟开始，持续时间为T分钟的任务视为从P点到P+T点连一条权为T的边。（边的起点是任务的起始时间，终点是任务结束时间的下一分钟）
如果一个点到最后也没有出度，则向后一个点连边权为0的边（没活干，这一分钟他可以摸鱼。。。）
跑最短路就得到他至少要干多长时间，答案就是（n-最短路结果）
如果将边权作为休息时间的话用最长路也能做
code:
```cpp
#include<cstdio>
#include<queue>
#include<cstring>
#define N 10005
using namespace std;
struct Edge{
int to,next,w;
}edge[N*2];
int head[N],tot;
void addedge(int from,int to,int w){
edge[++tot].to=to;
edge[tot].w=w;
edge[tot].next=head[from];
head[from]=tot;
}
int dis[N];
bool vis[N];
void spfa(){
memset(dis,0x7f,sizeof(dis));
dis[1]=0;
queue<int> q;
q.push(1);
int now;
while(!q.empty()){
now=q.front();
q.pop();
vis[now]=false;
for(int i=head[now];i;i=edge[i].next){
if(dis[edge[i].to]>dis[now]+edge[i].w){
dis[edge[i].to]=dis[now]+edge[i].w;
if(!vis[edge[i].to]){
q.push(edge[i].to);
vis[edge[i].to]=true;
}
}
}
}
}
int main(){
int n,k,p,t;
scanf("%d%d",&n,&k);
while(k--){
scanf("%d%d",&p,&t);
addedge(p,p+t,t);
}
for(int i=1;i<=n;++i){
if(head[i]==0){
addedge(i,i+1,0);
}
}
spfa();
printf("%d",n-dis[n+1]);
}
```