【 算法提高 道路和航路】（SPFA的SLF优化）

【 算法提高 道路和航路】（SPFA的SLF优化）

时间限制：1.0s 内存限制：256.0MB 问题描述 农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇（标号为1..T），这些城镇通过R条标号为（1..R）的道路和P条标号为（1..P）的航路相连。 每一条公路i或者航路i表示成连接城镇Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代价为Ci。每一条公路，Ci的范围为0<=Ci<=10,000；由于奇怪的运营策略，每一条航路的Ci可能为负的，也就是-10,000<=Ci<=10,000。 每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。 每一条航路都根据输入的Ai和Bi进行从Ai->Bi的单向通行。实际上，如果现在有一条航路是从Ai到Bi的话，那么意味着肯定没有通行方案从Bi回到Ai。 农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？配送中心位于城镇S中（1<=S<=T）。 输入格式 输入的第一行包含四个用空格隔开的整数T，R，P，S。 接下来R行，描述公路信息，每行包含三个整数，分别表示Ai，Bi和Ci。 接下来P行，描述航路信息，每行包含三个整数，分别表示Ai，Bi和Ci。 输出格式 输出T行，分别表示从城镇S到每个城市的最小花费，如果到不了的话输出NO PATH。 样例输入 6 3 3 4 1 2 5 3 4 5 5 6 10 3 5 -100 4 6 -100 1 3 -10 样例输出 NO PATH NO PATH 5 0 -95 -100 数据规模与约定 对于20%的数据，T<=100，R<=500，P<=500； 对于30%的数据，R<=1000，R<=10000，P<=3000； 对于100%的数据，1<=T<=25000，1<=R<=50000，1<=P<=50000。） 分析： SPFA及优化 链式前向星 明显，存在负权，求有向图的最短路。 可以用spfa， 但是在这里，普通的输入只得了80分，加一个输入输出挂，就多了10分。可能数据就是卡SPFA，貌似SPFA进行SLF优化。（…http://bubuko.com/infodetail-640133.html） 【90分代码】 #include using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) #define memc(a,b) memcpy(a,b,sizeof(b)) #define rep(i,a,n) for(int i=a;i=a;i--)///[n,a] #define pb push_back #define fi first #define se second #define IO ios::sync_with_stdio(false) #define fre freopen("in.txt","r",stdin) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; typedef unsigned long long ull; const double PI=acos(-1.0); const double E=2.718281828459045; const double eps=1e-3; const int INF=0x3f3f3f3f; const double dinf=0x3f3f3f3f+1.0; const int MOD=1e8+7; const int N=5e4+5; const ll maxn=1e6+5; const int dir[4][2]= {-1,0,1,0,0,-1,0,1}; struct Node { int to,w; int nxt; Node() {} Node(int to,int w,int nxt):to(to),w(w),nxt(nxt) {} } g[N<<2]; int head[N]; bool vis[N]; int dis[N],cnt=0; int t,r,p,s; inline void init() { mem(head,-1); mem(vis,0); } inline void addedge(int u,int v,int w) { g[cnt]= {v,w,head[u]}; head[u]=cnt++; } void spfa(int src) { mem(dis,INF); vis[src]=1; dis[src]=0; queueque; que.push(src); while(!que.empty()) { int now=que.front(); que.pop(); vis[now]=0; for(int i=head[now]; ~i; i=g[i].nxt) { Node e=g[i]; if(dis[e.to]>dis[now]+e.w) { dis[e.to]=dis[now]+e.w; if(!vis[e.to]) { vis[e.to]=1; que.push(e.to); } } } } } inline ll read() { ll r=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { r=(r<<3)+(r<<1)+ch-'0'; ch=getchar(); } return r*f; } inline void ouput(ll x) { if(x<0) { x=-x; putchar('-'); } if(x>9) ouput(x/10); putchar(x%10+'0'); } int main() { init(); t=read(),r=read(),p=read(),s=read(); int u,v,w; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。