SPFA in Java

一时兴起写了了个Java里的SPFA算法。。
。。C++0MSAC的题目我用Java要2000MS
不过我滥用了Java的特性。。类都开泛滥了。。一个SPFA开了五个类
题目是PKU 2387

import java.util.*;
class Edge
{
int t,c;
Edge(int _t,int _c)
{t=_t;c=_c;}
}
class Graph
{
int n;
List< List<Edge> > E;
Graph(int _n)
{
n=_n;
E=new ArrayList< List<Edge> >(n);
for(int i=0;i<n;i++) E.add(new ArrayList<Edge>());
}
void addEdge(int s,int t,int c)
{
E.get(s).add(new Edge(t,c));
E.get(t).add(new Edge(s,c));
}
Iterator<Edge> adj(int v)
{return E.get(v).iterator();}
}
class MyQueue extends ArrayDeque<Integer>
{
int n;boolean[] inQ;
MyQueue(int _n)
{
n=_n;
inQ=new boolean[n];
}
void put(int x)
{
if(!inQ[x])
{
super.add(x);
inQ[x]=true;
}
}
int get()
{
int t=super.poll();
inQ[t]=false;
return t;
}
}
class Spfa
{
final int inf=1<<29;
Graph G;
int[] dist;
MyQueue Q;
Spfa(Graph _G,int vs)
{
G=_G;
dist=new int[G.n];Arrays.fill(dist,inf);Q=new MyQueue(G.n);
dist[vs]=0;Q.put(vs);
while(!Q.isEmpty())
{
int t=Q.get();int cost=dist[t];
Iterator<Edge> i=G.adj(t);
while(i.hasNext())
{
Edge e=i.next();
int ncost=cost+e.c;
if(ncost<dist[e.t])
{
dist[e.t]=ncost;
Q.put(e.t);
}
}
}
}
int distTo(int v)
{
return dist[v];
}
}
public class Main
{
static Scanner in=new Scanner(System.in);
static public void main(String[] args)
{
int m=in.nextInt(),n=in.nextInt();
Graph G=new Graph(n);int s,t,c;
for(int i=0;i<m;i++)
{
s=in.nextInt();
t=in.nextInt();
c=in.nextInt();
G.addEdge(s-1,t-1,c);
}
Spfa solve=new Spfa(G,0);
System.out.println(solve.distTo(n-1));
}
}

本高亮代码使用codeHl生成,

TopCoder SRM 462 Div I 1000

比赛的时候没有A掉。。后来看了ikki大牛的提示算是明白了。。
由于n<=50想怎么写都行。。只要别暴力搜就可以了囧。。
首先枚举每条边。算出删掉这条边后从这条边的起点到2的最短路。。
为了方便可以把所有边的都反过来。。这样就都变成2到这个起点的最短路了。。
然后用spfa来更新答案。。就是说定义dist[i]从i节点运用最优策略到2的路程。。
那么关于j节点新的代价就是
删:deletecost of edge(j,i) /has been calculated before
不善:dist[i]+cost of edge(j,i)
那么新的代价就是这两个最大值。。
然后用这个来更新j节点。。跟平常的spfa一样就可以了。。
最后dist[0]就是所求了。。
Code:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

class WarTransportation {
public:
int messenger(int, vector <string>);
};
const int maxn=100,inf=1<<29;int n;
struct edge
{
int s,t,c,dcost;bool e;
edge(int _s,int _t,int _c):s(_s),t(_t),c(_c),e(true){}
};
vector<edge> E[maxn];
typedef vector<edge>::iterator it;
void add_edge(vector<edge> E[maxn],int s,int t,int c)
{E[s].push_back(edge(s,t,c));}
void spfa(vector<edge> E[maxn],it d)
{
d->e=false;int dist[maxn];rep(i,n) dist[i]=inf;
bool inq[maxn]={0};inq[1]=true;dist[1]=0;
queue<int> Q;Q.push(1);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(it i=E[t].begin();i!=E[t].end();i++)if(i->e)
{
int ncost=cost+i->c;
if(ncost<dist[i->t])
{
dist[i->t]=ncost;
if(!inq[i->t]) Q.push(i->t),inq[i->t]=true;
}
}
}
d->dcost=dist[d->t];d->e=true;
}
int WarTransportation::messenger(int _n, vector <string> h) {
n=_n;
string A;for(int i=0;i<h.size();i++) A+=h[i];
istringstream in(A);int s,t,c;char tmp;
do
{
in>>s>>t>>c;s–;t–;
add_edge(E,t,s,c);
}while(in>>tmp);
rep(i,n)
{
for(it e=E[i].begin();e!=E[i].end();e++)
spfa(E,e),cout<<e->t+1<<"->"<<e->s+1<<":"<<e->dcost<<endl;
}
int dist[maxn];rep(i,n) dist[i]=inf;
bool inq[maxn]={0};inq[1]=true;dist[1]=0;
queue<int> Q;Q.push(1);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(it i=E[t].begin();i!=E[t].end();i++)
{
int ncost=max(cost+i->c,i->dcost);
if(ncost<dist[i->t])
{
dist[i->t]=ncost;
if(!inq[i->t]) Q.push(i->t),inq[i->t]=true;
}
}
}
if(dist[0]==inf) return -1;
return dist[0];
}

//Powered by [KawigiEdit] 2.0!
本高亮代码使用codeHl生成,

TopCoder SRM DIV 1

God。。不知道怎么回事上次我直接变蓝色了。。结果这次进Div 1了。。
我很紧张。。结果发现第一题一看就是直接二分的题目。。然后我一高兴就直接写了。。
结果悲剧了。。实际上第一题是很triky的。。比如说“0000”这种test。。根本没想到。。
我房间一个人强到其他题一分没有。。光challenge就525。。我们房间基本上被cha光了。。
第二题反而是最水的。。直接模拟就可以了。。一开始我觉得n^2*S的复杂度会超。。
结果一点事都没有。。寒。。
第三题我没有想出算法。。写了个SB程序上去。。test1都过不了的那种。。
居然没人来cha我。。搞的我很想自cha。。结果不行的。。
我现在还是不知道怎么做啊。。感觉spfa式的递推应该是可以的。。
不过很难想出怎么写。。
我发现了想得分cha别人也是一种好途径。。尤其是一种题目BT到大家都想不出一些SB的case的时候。。
就可以爽了。。
最后99名。。就第二题做出来了。。变黄色了。。

两个梦。。

       很无聊的两个梦。。没我无聊就别看了。。
       由于我放寒假以来没有一天不是熬到4点钟以上的。。
昨天我的神经终于吃不消了。。又加上跟别人拼酒。终于倒了。。
7点就睡了。一直睡到今天中午12点才起来。。
N多天没有做梦的我终于做梦了。。
怎么说呢。。我记得我做了2个梦。第一个梦差不多忘光了。第二个梦记得还算清楚。。
由于记得不是很清楚。。有些地方只好自己乱DIE了。。
第一个梦我是梦见我没有任何原因(也许是有的。。但我忘了。。)来到了一个很SB的地方。。
那个地方好像是清朝初期跟8年前的安吉的混合体(汗。。)。。因为一开始还是一个小村落。。
走着走着就变成一个小城市了。。然后印象最深的就是我进了一个学校。。看到了很多小学的童鞋
然后我说你们怎么不回去。。他们说这里特自由。。不想走。。最后我还是逛了回儿。。然后乘地铁
走了(怎么会有地铁。。搞什么。。瀑布汗。。)。。
接下来就诡异了。。也可能是第二个梦。。就是我在坐地铁的时候。。地铁突然要翻了了。我敏锐的察觉到。。从天窗逃走了。。我们寝室的四个人也逃了还有一些人。。包括几个女生吧。。
地铁爆炸了。。人死光了。。
没错。。这就是死神来了的翻版。。然后WW莫名其妙死掉了(忘了死因)。。有个女的好像是看雪的时候被绊倒后被倒下来的杂货堆压住。。然后我和奔奔去救她。。结果等我翻出她。。她已经冻死了。。
我感觉不对了。。就打电话去叫另一个男的。。结果我看到一个人被烟火炸上了天。。掉下去摔死了。。
我们3个人(我奔奔和老大吧)。。吓个半死。。老大说自杀算了。。奔奔说好的。。
他们两个就自杀了(好像老大是盯着墙壁看了半天然后就莫名奇妙的死掉了。。奔奔是吼了声baidu你和谐我啊然后天上一道雷下来把他和谐了——就是不见了)。。。然后我也想自杀。。没有成功。。怎么也成功不了。。然后我就醒了。。

KLZ 毕业了。。

最近我沉迷于百度贴吧不能自拔。。经常熬夜在贴吧上闲逛。。
导致OI都没怎么搞。。实在很NC。。
不过由于我积极发帖。。所以在WOW得到了会员。。就是KLZ毕业了!
但是又由于我加入了刷2L党。。。就是看到2L就抢。被封ID封了10天。。
我真是该啊。。没事抢什么2L。。支持SJB!。。封我吧。。
不逛贴吧了。。搞搞OI了。。

SPOJ Select Teams

www.spoj.pl/problems/SELTEAM/
鄙视这种猥琐题。。
就是说从N个人中选择最多K个人组一个组,然后在这些人中选出一些人组成一个队。。再在这个队中选一个队长。。共有多少种办法。。
首先写一个暴力的。。是这样的。。

关键就在于后面那个式子。。按组合的意义就是说从i个数中选一个子集,并在子集中找一个队长。。
那么枚举这个队长。。其他的数就可以随便选。。所以:

我还是没有别的办法。。想了半天。。最后发现他要我们mod8388608
我分解了这个数。。发现

无语。。绝对的无语。。出题人太恶心了。。
那么只要枚举i-1到22就可以了。。23以上直接mod光了。。
代码:http://ideone.com/fgLc5VnR
提示:有时间一定要背2的乘方表了。。

写在情人节的。。

今天我TopCoder和COCI都悲剧之后。。非常郁闷。。去百度看直播了。。一直到现在。。
看到个男的在直播他的感情经历。。很有兴趣的看了看。。
结果一看就是3个小时。。。我真的有点怕了。。
他说的很对。。玩啥都行不要完感情。。被套牢了就追悔莫及了。。
爱情就是无中生有么。。人说到底就是只有自己的。。什么爱情即使在为对方也还是为自己。。
终究是矛盾的。。爱情如果搞到后面就是互相折磨了。。两个人真的不可能变成一个人的。。
知道这种也没用啊。。人也不是机器。。即使是幻影也还是蛮迷人的。。麻痹一下或许也可以吧。。
玩啥不要玩感情。。否则到头来被玩的只能是自己。。
o(︶︿︶)o 唉。。哥大学前坚决不谈恋爱了。。一心学习搞编程吧。。

TopCoder SRM Level 3

DP确实可以做。。但我无法debug。。
是这个样子的。。
设F[i][x]是name序列到第i个的时候。当前在input的x时的最短时间。。
为了简单起见只写F[x]
分四种情况
F[x]=(x-y)+F[y]=x+(F[y]-y)(y<x)
F[x]=(y-x)+F[y]=-x+(F[y]+y)(y>x)
F[x]=n-(x-y)+….
……
每种情况都可以弄的与x无关。。然后扫描四遍。。
但我无法Debug啊。。不知道怎么搞的

Page 3 of 712345...Last »