Sgu/103

来自NOCOW

SPFA即可计算函数特别纠结。

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
 
// false == blue	true == purple
 
using namespace std ;
 
ifstream fin ("input.txt");
ofstream fout ("output.txt");
 
const int MaxN= 301;
const int INF= 999999999;
 
typedef struct 
{
	bool Ini;
	int KeepIni;
	int Keep[2];
}RULE;
 
typedef struct
{
	int dot, prefix;
}NODE;
 
RULE R[MaxN];
int G[MaxN][MaxN], V[MaxN][MaxN];
int n, m;
int s, t;
int Dist[MaxN];
int Final= -1;
NODE Line[MaxN * MaxN* 2];
 
void Debug(int Num)
{
	fout << " " << R[Num].Ini << " " << R[Num].KeepIni << " " << R[Num].Keep[0] << " " << R[Num].Keep[1] << endl;
}
 
void Init()
{
	fin >> s >> t;
	fin >> n >> m ;
	for(int i(1); i<= n; ++ i)
	{
		char chr;
		int t1, t2, t3;
 
		//R[i].Clr[0]= false; R[i].Clr[1]= true;
		fin >> chr >> t1 >> t2 >> t3;
		//R[i].Ini= (chr == 'P');
		if(chr == 'P')
			R[i].KeepIni= t2+ t3- t1;
		else 
			R[i].KeepIni= t2- t1;
		R[i].Keep[0]= t2;
		R[i].Keep[1]= t2+ t3;
	}
	for(int i(1); i<= m; ++ i)
	{
		int t1, t2, val;
		fin >> t1 >> t2 >> val;
		G[t1][++G[t1][0]]= t2;
		V[t1][++V[t1][0]]= val;
		G[t2][++G[t2][0]]= t1;
		V[t2][++V[t2][0]]= val;
	}
}
 
int Calc(int a, int b, int t)
{
	int ta, tb, Tmp, Time;
 
	ta= (t+ R[a].KeepIni) % R[a].Keep[1];
	tb= (t+ R[b].KeepIni) % R[b].Keep[1];
	Time= 0;
 
	for(int i= 0; i< 10; ++ i)
		if(( ta < R[a].Keep[0] ) == (tb <  R[b].Keep[0] ))
		{
			return Time;
		}else
		{
			if(ta < R[a].Keep[0])
				Tmp= R[a].Keep[0]- ta;
			else
				Tmp= R[a].Keep[1]- ta;
			if(tb < R[b].Keep[0])
				Tmp= min(Tmp, R[b].Keep[0]- tb);
			else
				Tmp= min(Tmp, R[b].Keep[1]- tb);
			Time+= Tmp;
			ta= (ta + Tmp) % R[a].Keep[1];
			tb= (tb + Tmp) % R[b].Keep[1];
		}
	return -1;
}
 
void Print(int Pot)
{
	if(Line[Pot].prefix != -1)
		Print(Line[Pot].prefix);
	fout << Line[Pot].dot << " " ;
}
 
void SPFA()
{
	int p1, p2;
 
	p1= p2= 0;
	Line[0].dot= s; Line[0].prefix= -1;
	for(int i(0); i<= n; ++ i)Dist[i]= INF;
	Dist[s]= 0;
 
	for(; p1 <= p2; ++ p1)
	{
		int Now, Exp, Cst, Time;
 
		Now= Line[p1].dot;
		Time= Dist[Now];
		//fout << Now << " " << Time << " " << endl;
		for(int j(1); j<= G[Now][0]; ++ j)
		{
			Exp= G[Now][j];
			Cst= Calc(Now, Exp, Time);
			//fout << "--- " << Exp << " " << Cst << endl;
			if(Cst >= 0)
			{
				Cst+= V[Now][j];
				if(Dist[Now] + Cst <= Dist[Exp])
				{
					++p2;
					Line[p2].dot= Exp;
					Line[p2].prefix= p1;
					Dist[Exp]= Dist[Now] + Cst;
					if(Exp == t)Final= p2;
				}
			}
		}
	}
	//fout << "\n--------------" << endl;
	if(Final == -1)
		fout << "0" << endl;
	else
	{
		fout << Dist[t] << endl;
		Print(Final);
		fout << endl;
	}
	//system("pause");
}
 
int main()
{
	Init();
	SPFA();
	return 0;
}

By Strayer

//by abccbazj
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define M 100000
int n,m;
int st,en;
struct NODE{
       int c,b,p,r;
}node[310];
struct EDGE{
       int x,next,l;
}edge[28100];
int k[310];
int f[M];
int d[310];
bool v[310];
int tot,sum;
int pre[310];
int len[310];
int ans;
int min(int a,int b){return a<b?a:b;}
void add(int a,int b,int c){
     edge[++tot].x=b;
     edge[tot].l=c;
     edge[tot].next=k[a];
     k[a]=tot;
}
int wait(int x,int y,int t){
    int i,j;
    //初始状态比较 
    int tt=t;
    if (tt<node[x].r) i=node[x].c;
    else{
         tt=(t-node[x].r) % (node[x].p+node[x].b);
         int dd;
         if (node[x].c==0) dd=node[x].b;else dd=node[x].p;
         if (tt>=0 && tt<dd) i=!node[x].c;else i=node[x].c;
    }
    //------------------------------
    tt=t;
    if (tt<node[y].r) j=node[y].c;
    else{
         tt=(t-node[y].r) % (node[y].b+node[y].p);
         int dd;
         if (node[y].c==0) dd=node[y].b;else dd=node[y].p;
         if (tt>=0 && tt<dd) j=!node[y].c;else j=node[y].c;
    }
    if (i==j) return 0;
    //不同进入第一次变灯 
    int tx,ty;
    if (t<node[x].r) tx=node[x].r;
    else{
         int mid=(t-node[x].r) % (node[x].b+node[x].p);
         int dd;
         if (node[x].c==0) dd=node[x].b;else dd=node[x].p;
         if (mid>=0 && mid<dd) tx=t-mid+dd;
         else tx=t-mid+(node[x].b+node[x].p);
    }
    //------------------------------
    if (t<node[y].r) ty=node[y].r;
    else{
         int mid=(t-node[y].r) % (node[y].b+node[y].p);
         int dd;
         if (node[y].c==0) dd=node[y].b;else dd=node[y].p;
         if (mid>=0 && mid<dd) ty=t-mid+dd;
         else ty=t-mid+(node[y].b+node[y].p);
    }
    if (tx!=ty) return min(tx,ty)-t;
    //第一次编订后仍不同进入第二次变灯 
    int mid=(tx-node[x].r) % (node[x].b+node[x].p); 
    int dd;
    if (node[x].c==0) dd=node[x].b;else dd=node[x].p;
    if (mid>=0 && mid<dd) tx=tx-mid+dd;
    else tx=tx-mid+(node[x].b+node[x].p);
    //------------------------------
    mid=(ty-node[y].r) % (node[y].b+node[y].p);
    if (node[y].c==0) dd=node[y].b;else dd=node[y].p;
    if (mid>=0 && mid<dd) ty=ty-mid+dd;
    else ty=ty-mid+(node[y].b+node[y].p);
    if (tx!=ty) return min(tx,ty)-t;
    //第二次变灯后仍不同进入第三次变灯
    mid=(tx-node[x].r) % (node[x].b+node[x].p); 
    if (node[x].c==0) dd=node[x].b;else dd=node[x].p;
    if (mid>=0 && mid<dd) tx=tx-mid+dd;
    else tx=tx-mid+(node[x].b+node[x].p);
    //------------------------------
    mid=(ty-node[y].r) % (node[y].b+node[y].p);
    if (node[y].c==0) dd=node[y].b;else dd=node[y].p;
    if (mid>=0 && mid<dd) ty=ty-mid+dd;
    else ty=ty-mid+(node[y].b+node[y].p);
    if (tx!=ty) return min(tx,ty)-t;
    //第三次编订后仍不同进入第四次变灯
    mid=(tx-node[x].r) % (node[x].b+node[x].p); 
    if (node[x].c==0) dd=node[x].b;else dd=node[x].p;
    if (mid>=0 && mid<dd) tx=tx-mid+dd;
    else tx=tx-mid+(node[x].b+node[x].p);
    //------------------------------
    mid=(ty-node[y].r) % (node[y].b+node[y].p);
    if (node[y].c==0) dd=node[y].b;else dd=node[y].p;
    if (mid>=0 && mid<dd) ty=ty-mid+dd;
    else ty=ty-mid+(node[y].b+node[y].p);
    if (tx!=ty) return min(tx,ty)-t;
    //第四次编订后仍不同进入第五次变灯
    mid=(tx-node[x].r) % (node[x].b+node[x].p);
    if (node[x].c==0) dd=node[x].b;else dd=node[x].p;
    if (mid>=0 && mid<dd) tx=tx-mid+dd;
    else tx=tx-mid+(node[x].b+node[x].p);
    //------------------------------
    mid=(ty-node[y].r) % (node[y].b+node[y].p);
    if (node[y].c==0) dd=node[y].b;else dd=node[y].p;
    if (mid>=0 && mid<dd) ty=ty-mid+dd;
    else ty=ty-mid+(node[y].b+node[y].p);
    if (tx!=ty) return min(tx,ty)-t;
    //无法通行 
    return -1;
}
//最短路求解 
void SPFA(){
     int head=0,tail=1;
     memset(d,63,sizeof(d));
     memset(v,0,sizeof(v));
     d[st]=0;
     v[st]=true;
     f[tail]=st;
     while (head!=tail){
           head++;
           if (head==M) head=1;
           int x=f[head];
           v[x]=false;
           for (int t=k[x];t;t=edge[t].next){
               int tmp=wait(x,edge[t].x,d[x]);
               if (tmp!=-1 && d[edge[t].x]>d[x]+tmp+edge[t].l){
                                              d[edge[t].x]=d[x]+tmp+edge[t].l;
                                              pre[edge[t].x]=x;
                                              if (!v[edge[t].x]){
                                                              v[edge[t].x]=true;
                                                              tail++;
                                                              if (tail==M) tail=1;
                                                              f[tail]=edge[t].x;
                                              }
               }
           }
     }
     ans=d[en];
}    
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d\n",&st,&en);
    if (st==en){
                printf("0\n%d\n",st);
                return 0;
    }
    scanf("%d%d\n",&n,&m);
    for (int i=1;i<=n;i++){
        char c;
        scanf("%c%d%d%d\n",&c,&node[i].r,&node[i].b,&node[i].p);
        node[i].c=('B'==c);
    }
    for (int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    SPFA();
    if (ans>100000){printf("0\n");return 0;}
    printf("%d\n",ans);
    len[++sum]=en;
    int t=pre[en];
    while (t){
          len[++sum]=t;
          t=pre[t];
    }
    for (int i=sum;i>1;i--) printf("%d ",len[i]);
    printf("%d\n",len[1]);
    return 0;
}

by hza
#include<cstdio>
 
const int INF=100000000;
const int MAX=300+10;
int n,m,S,T;
int r[MAX],t[MAX][2];
bool first[MAX];
char a[2];
int map[MAX][MAX];
 
int color(int i,int time)
{
	if(time<r[i])
		return first[i];
	else
	{
		int k=(time-r[i])%(t[i][1]+t[i][0]);
		if(first[i]==1)
			return k<t[i][0]?0:1;
		else return k<t[i][1]?1:0;
	}
}
 
int less(int i,int time)
{
	if(time<r[i])
		return r[i];
	else
	{
		int k=(time-r[i])%(t[i][1]+t[i][0]);
		int begin=time-k;
		if(first[i]==1)
			return k<t[i][0]?begin+t[i][0]:begin+t[i][1]+t[i][0];
		else 
			return k<t[i][1]?begin+t[i][1]:begin+t[i][1]+t[i][0];
	}
}
 
int min(int a,int b)
{
	return a<b?a:b;
}
 
int wait(int k,int l,int time,bool f)
{
	if(color(k,time)==color(l,time))
		return time;
	int t1=less(k,time),t2=less(l,time);
	if(t1==t2)
	{
		if(!f)
		{
			return wait(k,l,t1,1);
		}else if(time<=r[k]||time<=r[l])
			return wait(k,l,t1,1);
		else return INF;
	}
	return min(t1,t2);
}
 
int q[MAX*10],begin=0,now,end=0,dist[MAX],hash[MAX],last[MAX];
int stack[MAX];
 
void SPFA()
{
	int next,y,i;
	for(i=1;i<=n;++i)dist[i]=INF;
	q[end++]=S;dist[S]=0;
	hash[S]=1;last[S]=0;
	while(begin<end)
	{
		now=q[begin++];
		for(next=1;next<=n;++next)
		{
			if(map[now][next])
			{
				y=wait(now,next,dist[now],0);
				if(y==INF)continue;
				if(y+map[now][next]<dist[next])
				{
					dist[next]=y+map[now][next];
					last[next]=now;
					if(!hash[next])
					{
						hash[next]=1;
						q[end++]=next;
					}
				}
			}
		}
		hash[now]=0;
	}
	if(dist[T]==INF)
	{
		printf("0");
		return;
	}
	now=T;
	while(now)
	{
		stack[++stack[0]]=now;
		now=last[now];
	}
	printf("%d\n",dist[T]);
	for(i=stack[0];i>=1;--i)
		printf("%d ",stack[i]);
	printf("\n");
}
 
int main()
{
	freopen("103.in","r",stdin);
	freopen("103.out","w",stdout);
	int i,x,y;
	scanf("%d %d %d %d",&S,&T,&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%s",a);
		if(a[0]=='B')
			first[i]=0;
		else first[i]=1;
		scanf("%d %d %d",&r[i],&t[i][0],&t[i][1]);
	}
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		scanf("%d",&map[x][y]);
		map[y][x]=map[x][y];
	}
	SPFA();
}

/by Logic
#include<stdio.h>
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=350,big=100000000;
int n,m,st,en,ci[maxn],ric[maxn],ti[maxn][2],la[maxn],ans=0,pa[maxn],l;
int e[maxn][maxn];
int d[maxn],vis[maxn]={0};
int judg(int x,int t)
{
	int res=ci[x];
	if(t>=ric[x])
	{
		t-=ric[x];
		res=(res+1)&1;
		t%=ti[x][0]+ti[x][1];
		if(t>=ti[x][res]) res=(res+1)&1;
	}
	return res;
}
int calc(int x,int y)
{
	int t=d[x],t0=0;
	while(judg(x,t+t0)!=judg(y,t+t0)&&t0<10000) t0++;
	if(t0>=10000) return big;
	return t+t0+e[x][y];
}
void dijk()
{ 
	int i,j,now,min0,dis;
	for(i=1;i<=n;i++)
		d[i]=big;
	d[st]=0;
	for(i=0;i<n;i++)
	{
		min0=big,now=0;
		for(j=1;j<=n;j++)
			if(!vis[j]&&d[j]<min0) min0=d[j],now=j;
		if(!now) break;
		for(j=1;j<=n;j++)
			if(!vis[j]&&e[now][j]<big)
			{
				dis=calc(now,j);
				if(d[j]>dis) d[j]=dis,la[j]=now;
			}
		vis[now]=1;
	}
	if(d[en]!=big) ans=d[en];
}
int main()
{
	freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	int i,j,x,y,li;
	char cc;
	scanf("%d%d%d%d\n",&st,&en,&n,&m);
	for(i=1;i<=n;i++)
		scanf("%c %d%d%d\n",&cc,&ric[i],&ti[i][0],&ti[i][1]),ci[i]=(cc=='B')?0:1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			e[i][j]=big;
	for(i=0;i<m;i++)
		scanf("%d%d%d",&x,&y,&li),e[x][y]=e[y][x]=li;
	dijk();	
	printf("%d\n",ans);
	if(ans)
	{
		for(i=en,l=0;i;i=la[i],l++)
			pa[l]=i;
		for(i=l-1;i;i--)
			printf("%d ",pa[i]);
		printf("%d\n",en);
	}
	return 0;
}

[编辑] ==========================================================================================

by a710128 (dijkstra)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue> 
#include<vector>
using namespace std;
struct Junctions
{
	char col;
	int rtm,tb,tp;
	vector<int>g,far;
}dt[305];
struct Data
{
	int fs,se;
	bool operator < (const Data &b)const{return fs>b.fs;}
	Data(int _f,int _s){fs=_f;se=_s;}
};
const int INF=0x3f3f3f3f;
bool vis[305];
int S,T,n,m,tpa,tpb,tpc,fa[305],dis[305],ans[305];
bool color(int x1,int time)
{
	int t=dt[x1].rtm-dt[x1].tb;
	if(dt[x1].col=='P') t-=dt[x1].tp;
	if((time-t)%(dt[x1].tb+dt[x1].tp)<dt[x1].tb) return true;
	return false;
}
inline int gettime(int x1,int time)
{
	int t=dt[x1].rtm-dt[x1].tb;
	if(dt[x1].col=='P') t-=dt[x1].tp;
	t=(time-t)%(dt[x1].tb+dt[x1].tp);
	if(t<dt[x1].tb) return dt[x1].tb-t;
	return dt[x1].tb+dt[x1].tp-t;
}
int nexttime(int x1,int x2,int time)
{
	int k=0;bool c1=color(x1,time),c2=color(x2,time);
	while(c1!=c2)
	{
		if(k==2) return INF;
		time+=min(gettime(x1,time),gettime(x2,time));
		c1=color(x1,time);c2=color(x2,time);
		k++;
	}
	return time;
}
int main()
{
	scanf("%d%d%d%d",&S,&T,&n,&m);
	for(int i=1;i<=n;i++) scanf("%s%d%d%d",&dt[i].col,&dt[i].rtm,&dt[i].tb,&dt[i].tp);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&tpa,&tpb,&tpc);
		dt[tpa].g.push_back(tpb);
		dt[tpa].far.push_back(tpc);
		dt[tpb].g.push_back(tpa);
		dt[tpb].far.push_back(tpc);
	}
	memset(dis,0x3f,sizeof(dis));
	priority_queue<Data>q;
	q.push(Data(0,S));dis[S]=0;
	while(!q.empty())
	{
		Data now=q.top();q.pop();
		if(vis[now.se]) continue;
		vis[now.se]=true;
		for(int i=0;i<(int)dt[now.se].g.size();i++)
			if(!vis[dt[now.se].g[i]])
			{
				int nt=nexttime(now.se,dt[now.se].g[i],now.fs)+dt[now.se].far[i];
				if(nt<dis[dt[now.se].g[i]])
				{
					dis[dt[now.se].g[i]]=nt;
					fa[dt[now.se].g[i]]=now.se;
					q.push(Data(nt,dt[now.se].g[i]));
				}
			}
	}
	if(!vis[T]) printf("0");
	else
	{
		printf("%d\n",dis[T]);
		for(int i=T;i;i=fa[i]) ans[++ans[0]]=i;
		for(int i=smkk[0];i>=1;i--) printf("%d ",ans[i]);
	}
	return 0;
}

Sgu/103

[编辑] ==========================================================================================

查看

个人工具

导航

搜索

工具箱