消息处理器（40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base=233;
const int MAXN=1e4+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define lson rt<<1,l,mid
#define endll printf("\n")
#define pii pair<int, int>
#define rson rt*2+1,mid+1,r
#define s1(a) scanf("%d",&a)
#define stop system("pause")
#define lowbit(x) ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int T,n,m;
struct IN
{
int u,v,op,t;//
IN (int uu,int vv,int oo,int tt):u(uu),v(vv),op(oo),t(tt){};
friend bool operator <(IN a,IN b)
{
if(a.t!=b.t) return a.t<b.t;
return a.op<b.op;
}
};
priority_queue<IN>q;
int main()
{
scanf("%d %d\n",&T,&n);
while(T--)
{
while(!q.empty()) q.pop();
string s;
for(int i=0;i<n;i++)
{
getline(cin,s);
int len=s.size(),tt=0;
for(int j=0;j<len;j+=3)
{
if(s[j]=='S')
q.push(IN(i,s[j+1]-'0',1,tt++));
else
q.push(IN(s[j+1]-'0',i,2,tt++));
}
}
queue<IN>pp[MAXN];
int size=0;
while(!q.empty())
{
IN tmp=q.top();q.pop();
int u=tmp.u,v=tmp.v;
if(tmp.op==1)
{
IN tmp2=IN(u,v,1,1);
if(pp[v].empty())
{
pp[u].push(tmp2);
size++;
}
else
{
IN tmp3=pp[v].front();
if(tmp3.op==2&&tmp3.u==u)
{
pp[v].pop();
if(pp[v].empty()) size--;
}
else pp[u].push(tmp2);
}
}
else
{
IN tmp2=IN(u,v,2,1);
if(pp[u].empty())
{
pp[v].push(tmp2);
size++;
}
else
{
IN tmp3=pp[u].front();
if(tmp3.op==1&&tmp3.v==v)
{
pp[u].pop();
if(pp[u].empty()) size--;
}
else pp[v].push(tmp2);
}
}
}
if(size) printf("1\n");
else printf("0\n");
}
//stop;
return 0;
} 淦，我是傻子嘛，想到了队列模拟都没想到根本不用判断时间
100分代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base=233;
const int MAXN=1e4+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define lson rt<<1,l,mid
#define endll printf("\n")
#define pii pair<int, int>
#define rson rt*2+1,mid+1,r
#define s1(a) scanf("%d",&a)
#define stop system("pause")
#define lowbit(x) ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int T,n,m;
struct IN
{
int u,v,op;//
IN (int uu,int vv,int oo):u(uu),v(vv),op(oo){};
};
string s;
queue<IN>q[MAXN];
int main()
{
scanf("%d %d\n",&T,&n);
while(T--)
{
for(int i=0;i<n;i++)
{
while(q[i].size()) q[i].pop();
getline(cin,s);
int len=s.size();
int op;
for(int j=0;j<len;)
{
if(s[j]=='S') op=1;
else if(s[j]=='R') op=2;
j++;
int num=0;
while(s[j]>='0'&&s[j]<='9')
num=num*10+s[j]-'0',j++;
q[i].push(IN(i,num,op));
j++;
}
}
while(1)
{
bool flag=false;
for(int i=0;i<n;i++)
{
if(q[i].empty()) continue;
IN tmp=q[i].front();
if(q[tmp.v].empty()) break;
IN tmp2=q[tmp.v].front();
if(tmp2.op+tmp.op==3&&tmp2.v==i)
{
q[i].pop();
q[tmp.v].pop();
flag=true;
i--;
}
}
if(!flag) break;
}
bool flag=true;
for(int i=0;i<n;i++)
{
if(q[i].size())
{
printf("1\n");
flag=false;break;
}
}
if(flag) printf("0\n");
}
return 0;
}
交通规划
单源最短路都这么明显了！不要乱想别的了。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base=233;
const int MAXN=1e5+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define lson rt<<1,l,mid
#define endll printf("\n")
#define pii pair<int, int>
#define rson rt*2+1,mid+1,r
#define s1(a) scanf("%d",&a)
#define stop system("pause")
#define lowbit(x) ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
struct Graph
{
int tot,head[MAXN];
struct IN{int v,next,w;}edge[MAXN<<1];
void init(){mem(head,-1);tot=0;}
void addedge(int u,int v,int w)
{
edge[tot].v=v;edge[tot].w=w;
edge[tot].next=head[u];head[u]=tot++;
}
int Start(int u){return head[u];}
int To(int i){return edge[i].v;}
int Val(int i){return edge[i].w;}
int Next(int i){return edge[i].next;}
}G;
int n,m;
int dis[MAXN],vis[MAXN];
void input()
{
s2(n,m);G.init();
for(int i=0;i<m;i++)
{
int u,v,w;s3(u,v,w);
G.addedge(u,v,w);
G.addedge(v,u,w);
}
}
int cost[MAXN];
int dij(int x)//x=start
{
priority_queue<pii > q;// 第一关键字为距离，第二关键字为点
mem(dis,INF);mem(vis,0);
q.push(make_pair(0,x));
dis[x]=0;
while(q.size())
{
int u=q.top().second; //取出点
q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int i=G.Start(u);~i;i=G.Next(i))
{
int v=G.To(i);
if (dis[v]>dis[u]+G.Val(i))
{
dis[v]=dis[u]+G.Val(i);
cost[v]=G.Val(i);
//因为更新到某点的最短路肯定是前面的最短路加了一条边（仅仅一条）
//所以每条边的花费仅仅为新增加的这一条
q.push(make_pair(-dis[v],v));
//入堆,因为需要最小的边所以这里丢进去负值用于排序
}
else if(dis[v]==dis[u]+G.Val(i))
cost[v]=min(cost[v],G.Val(i));//
}
}
int ans=0;
for(int i=2;i<=n;i++)
ans+=cost[i];
return ans;
}
int main()
{
input();
mem(cost,0);
printf("%d\n",dij(1));
//stop;
return 0;
} 送货（DFS非递归 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base=233;
const int MAXN=1e4+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define lson rt<<1,l,mid
#define endll printf("\n")
#define pii pair<int, int>
#define rson rt*2+1,mid+1,r
#define s1(a) scanf("%d",&a)
#define stop system("pause")
#define lowbit(x) ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
//原始数据
int n,m;
set<int>g[MAXN];
//判断连通性
int pre[MAXN],du[MAXN];
int fund(int x){return x==pre[x]?x:pre[x]=fund(pre[x]);}
void join(int x,int y){pre[fund(x)]=fund(y);}
//求欧拉路
stack<int>path;
bool vis[MAXN][MAXN];
int nxt(int u)
{
set<int>::iterator it;
for(it=g[u].begin();it!=g[u].end();it++)
if(!vis[u][*it]) return *it;
return -1;
}
void dfs(int s)
{
stack<int>st;
st.push(s);
while(!st.empty())
{
int u=st.top();
int v=nxt(u);
if(v!=-1)
{
vis[u][v]=vis[v][u]=true;
st.push(v);
}
else
{
st.pop();
path.push(u);
}
}
}
int main()
{
s2(n,m);
for(int i=0;i<=n;i++) pre[i]=i,du[i]=0;
for(int i=0;i<m;i++)
{
int u,v;s2(u,v);
g[u].insert(v);
g[v].insert(u);
if(fund(u)!=fund(v))
join(u,v);
du[u]++;du[v]++;
}
//判断连通性
int cnt=0,tag=0;
for(int i=1;i<=n;i++)
{
if(i==pre[i]) cnt++;
if(du[i]%2) tag++;
}
if(cnt>1||(tag!=0&&tag!=2))
{
printf("-1\n");
return 0;
}
//
mem(vis,0);
dfs(1);
while(!path.empty())
{
printf("%d ",path.top());
path.pop();
}
endll;
//stop;
return 0;
} 游戏（BFS #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base=233;
const int MAXN=1e6+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define lson rt<<1,l,mid
#define endll printf("\n")
#define pii pair<int, int>
#define rson rt*2+1,mid+1,r
#define s1(a) scanf("%d",&a)
#define stop system("pause")
#define lowbit(x) ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m,t;
struct I
{
int a,b;
}lim[111][111];
struct IN
{
int x,y,t;
IN(){};
IN(int xx,int yy,int tt):x(xx),y(yy),t(tt){};
};
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
bool vis[110][110][333];
int check(int x,int y,int t)
{
if(x<=0||y<=0||x>n||y>m||vis[x][y][t]) return 0;
if(lim[x][y].a<=t&&lim[x][y].b>=t) return 0;
return 1;
}
int bfs()
{
queue<IN>q;
q.push(IN(1,1,0));
vis[1][1][0]=true;
while(q.size())
{
int x=q.front().x,y=q.front().y,t=q.front().t;
q.pop();
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i],nt=t+1;
if(check(nx,ny,nt))
{
if(nx==n&&ny==m) return nt;
vis[nx][ny][nt]=true;
q.push(IN(nx,ny,nt));
}
}
}
return -1;
}
int main()
{
s3(n,m,t);
mem(lim,-1);mem(vis,false);
for(int i=0;i<t;i++)
{
int r,c,a,b;s2(r,c);s2(a,b);
lim[r][c].a=a,lim[r][c].b=b;
}
printf("%d\n",bfs());
//stop;
return 0;
}
京公网安备 11010502036488号