例题1 interval
- 最长路
- 数组下标为-1怎么处理
- ”标准输出太巨怎么办“
/*
reference:
translation:
solution:
1---->在a[i]和b[i]+1之间连一条长度为c[i]的有向边
2---->在i和i+1之间连一条长度为0的有向边
3---->在i+1和i之间连一条长度为-1的有向边
trigger:
note:
*我们在i-1和i之间连长度为0的有向边，在i和i-1之间连长度为-1的有向边
因为i的范围是0-50000所以i-1会变成负数，我们都知道，若数组的下标为负，程序会运行
错误，所以我们不妨给所有的变量加1，这样就不会出现负下标了
date:
2019.09.05
*/
const int N=1e6+10;
int head[N],edge_num,maxx=INT_MIN,minn=INT_MAX;
int n,m,s;
int dis[N];
bool vis[N];
struct edge{
int v,w,next;
}e[N];
inline void add(int u,int v,int w){e[++edge_num].v=v;e[edge_num].w=w;e[edge_num].next=head[u];head[u]=edge_num;}
queue<int>q;
inline void spfa(){
mem(dis,-0x3f);
mem(vis,0);
q.push(0);
vis[0]=1;
dis[0]=0;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
ee(i,u){
int v=e[i].v,w=e[i].w;
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
#undef int
int main(){
#define int long long
#ifdef WIN32
freopen("interval.txt","r",stdin);
#endif
int T;rd(T);
rep(cases,1,T){
//初始化；
mem(e,0);mem(head,0);
edge_num=0,maxx=INT_MIN,minn=INT_MAX;
rd(m);
while(m--){
int b,e,t;rd(b),rd(e),rd(t);
add(b,e+1,t);
maxx=max(maxx,e+1);
}
rep(i,0,maxx){
add(i+1,i,-1);
add(i,i+1,0);
}
spfa();
if(cases<T)printf("%lld
",dis[maxx]);
else printf("%lld",dis[maxx]);
}
return 0;
}
例二（看似很裸）poj 3159 candies
- poj 交的时候不能在文本末尾写注释
- spfa+queue竟然超时是什么鬼！！！，spfa只能加数组才能过！！！连加双端队列优化都不可以………………仙人板板
/*
reference:
translation:
solution:
trigger:
note:
*
date:
2019.09.04
*/
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define ee(i,x) for(int i=head[x];i;i=e[i].next)
#define mem(a,b) memset(a,b,sizeof(a))
const int N = 30010,M = 150010;
int head[N],edge_num;
int n,m,dis[N];
bool vis[N];
struct edge{
int v,w,next;
}e[M];
inline void add(int u,int v,int w){e[++edge_num].v=v;e[edge_num].w=w;e[edge_num].next=head[u];head[u]=edge_num;}
//inline void adde(int u,int v){e[++edge_num].v=v;e[edge_num].next=head[u];head[u]=edge_num;}
/*
deque<int>q;
inline void spfa(){
mem(dis,0x3f);
mem(vis,0);
q.push_back(1);
vis[1]=1;
dis[1]=0;
while(!q.empty()){
int u=q.front();q.pop_front();
vis[u]=0;
ee(i,u){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(q.empty() || dis[v]<dis[u])
q.push_front(v);
else q.push_back(v);
vis[v]=1;
}
}
}
}*/
int q[N];
void spfa(int start,int n)
{
int top=0;
for(int v=1;v<=n;v++)//初始化
{
if(v==start)
{
q[top++]=v;
vis[v]=true;
dis[v]=0;
}
else
{
vis[v]=false;
dis[v]=0x3f3f3f3f;
}
}
while(top!=0){
int u=q[--top];
vis[u]=0;
ee(i,u){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=true;
q[top++]=v;
}
}
}
}
}
int main(){
rd(n),rd(m);
while(m--){
int u,v,w;rd(u),rd(v),rd(w);
add(u,v,w);
}
spfa(1,n);
printf("%d
",dis[n]);
return 0;
}
/*
2 2
1 2 5
2 1 4
*/
//5