Description
在一個遙遠的世界裡有兩個國家：位於大陸西端的傑森國和位於大陸東端的 克裡斯國。兩個國家的人民分別信仰兩個對立的神：傑森國信仰象征黑暗和毀滅 的神曾·布拉澤，而克裡斯國信仰象征光明和永恆的神斯普林·布拉澤。 幻想歷 8012年 1月，傑森國正式宣布曾·布拉澤是他們唯一信仰的神，同 時開始迫害在傑森國的信仰斯普林·布拉澤的克裡斯國教徒。 幻想歷 8012年 3月2日，位於傑森國東部小鎮神谕鎮的克裡斯國教徒發動 起義。 幻想歷 8012年 3月7日，神谕鎮的起義被傑森國大軍以殘酷手段鎮壓。 幻想歷 8012年 3月8日，克裡斯國對傑森國宣戰。由數十萬大軍組成的克
裡斯軍團開至兩國邊境，與傑森軍團對峙。 幻想歷 8012年 4月，克裡斯軍團攻破傑森軍團防線進入神谕鎮，該鎮幸存 的克裡斯國教徒得到解放。 戰爭隨後進入膠著狀態，曠日持久。戰況慘烈，一時間槍林彈雨，硝煙彌漫， 民不聊生。 幻想歷 8012年 5月12日深夜，斯普林·布拉澤降下神谕：“Trust me, earn eternal life.”克裡斯軍團士氣大增。作為克裡斯軍團的主帥，你決定利用這一機 會發動奇襲，一舉擊敗傑森國。具體地說，傑森國有 N 個城市，由 M條單向道 路連接。神谕鎮是城市 1而傑森國的首都是城市
N。你只需摧毀位於傑森國首都 的曾·布拉澤大神殿，傑森國的信仰，軍隊還有一切就都會土崩瓦解，灰飛煙滅。 為了盡量減小己方的消耗，你決定使用自爆機器人完成這一任務。唯一的困 難是，傑森國的一部分城市有結界保護，不破壞掉結界就無法進入城市。而每個 城市的結界都是由分布在其他城市中的一些結界發生器維持的，如果想進入某個 城市，你就必須破壞掉維持這個城市結界的所有結界發生器。 現在你有無限多的自爆機器人，一旦進入了某個城市，自爆機器人可以瞬間 引爆，破壞一個目標（結界發生器，或是傑森國大神殿），當然機器人本身也會
一起被破壞。你需要知道：摧毀傑森國所需的最短時間。
Input
第一行兩個正整數 N, M。 接下來 M行，每行三個正整數 ui, vi, wi，表示有一條從城市ui到城市 vi的單 向道路，自爆機器人通過這條道路需要 wi的時間。 之後 N 行，每行描述一個城市。首先是一個正整數 li，維持這個城市結界所 使用的結界發生器數目。之後li個1~N 之間的城市編號，表示每個結界發生器的 位置。如果 Li = 0，則說明該城市沒有結界保護，保證L1 = 0 。
Output
僅包含一個正整數 ，擊敗傑森國所需的最短時間。
Sample Input
6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5
Sample Output
5
HINT
對於 20%的數據，滿足 N≤15，M≤50；
對於 50%的數據，滿足 N≤500，M≤6,000；
對於 100%的數據，滿足 N≤3,000，M≤70,000，1≤wi≤108
。
輸入數據保證一定有解，且不會存在維持某個城市結界的結界發生器在這個
城市內部。
連接兩個城市的道路可能不止一條， 也可能存在一個城市自己到自己的道路。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KCjxicj4KPC9oMj4KPGJyPgoKPGJyPgoK1eK1wMziysfSu7XAtPjP3tbGtcTX7rbMwrfOyszio6zK18/I0OjSqrTdu9m52M+1zby1xMjrsd+21NOmtcS147LFxNy1vcv7o6zG5LTOv8nS1M2syrHX37bguPa146GjCsrXz8i/vMLHzqy7pMG9uPbK/dfpo6zSu7j2ysfU3cfSsru/vMLHtbHHsLXjtcTI67HftcTX7rbMvuDA62hbXaOs0ru49srH1ebKtbXEvuDA62Rpc1tdo6y/vMLH08NzcGZh1/ajrMO/tM64/NDCwcvSu7j2tePV5sq1tcTX7rbMvuDA66Osvs29q8v7vNPI67bTwdCjrL+0yse38cTcuPzQwsbky/u1xLXjo6y21NPaw7/Su7TOuPzQwqOstrzSqsmo0rux6b+0y/vL+dPQx7DH/bXE1+62zL7gwOujrMv50tTKsbzkuLTU07bIvs3Kx08oTl4zKdfz09Khowo8YnI+Cgo8cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
#include
#include
#include
using namespace std;
int get_int(){
int x=0;char c;int t=0;
for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
if (c=='-'){t=1;c=getchar();}
for (;c>='0'&&c<='9';c=getchar()){x*=10;x+=c-48;}
if (t) x=-x;return x;
}
const int maxn=3050,maxm=70050;
int n,m;
long long inf;
int heap[maxn][maxn],tal[maxn];
int stay[maxn];
long long d[maxn],f[maxn];
int first[maxn],to[maxm],next[maxm],w[maxm],size;
void put(int x,int y,int ww)
{
size++;
next[size]=first[x];
first[x]=size;
to[size]=y;
w[size]=ww;
}
int first_[maxn],to_[maxn*maxn/2],next_[maxn*maxn/2];
void put_(int x,int y)
{
size++;
next_[size]=first_[x];
first_[x]=size;
to_[size]=y;
}
void init()
{ inf=(1<<29);
inf=inf*inf;
n=get_int(),m=get_int();
for (int i=1;i<=n;i++) f[i]=d[i]=inf;
d[1]=0;
f[1]=0;
for (int i=1;i<=m;i++)
{
int x=get_int(),y=get_int(),ww=get_int();
if (x!=y) put(x,y,ww);
}
size=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) stay[j]=0;
for (int j=get_int();j;j--)
{int x=get_int();
if (!stay[x]);
{
tal[i]++;
heap[i][tal[i]]=x;
stay[x]=1;
//up(i,tal[i]);
put_(x,i);
}
}
}
}
int line[maxn*5],mod=maxn*5-50;
bool upmin(long long &x,long long y)
{
if (yx) {x=y;return true;}
return false;
}
bool ban(int v)
{
long long ans=f[v];
f[v]=d[v];
for (int i=1;i<=tal[v];i++) upmax(f[v],f[heap[v][i]]);
//printf("ans = %I64d f[%d] =%I64d\n",ans,v,f[v]);
if (f[v]mod) tou=1;
for (int k=first[line[tou]];k;k=next[k])
{
upmin(d[to[k]],f[line[tou]]+w[k]);
if (ban(to[k]))
{//printf(" ok ban %d\n",to[k]);
if (!stay[to[k]])
{
// printf(" ok %d\n",to[k]);
wei++;
if (wei>mod) wei=1;
line[wei]=to[k];
stay[to[k]]=1;
}
}
}
for (int k=first_[line[tou]];k;k=next_[k])
{//printf("try ban %d\n",to_[k]);
if (ban(to_[k]))
{//printf(" ok ban %d\n",to[k]);
if (!stay[to_[k]])
{
//printf(" ok %d\n",to[k]);
wei++;
if (wei>mod) wei=1;
line[wei]=to_[k];
stay[to_[k]]=1;
}
}
}
stay[line[tou]]=0;
// printf("tou = %d wei =%d\n",tou,wei);
// for (int i=tou;i<=wei;i++)
// printf("%d ",line[i]);printf("\n");
// for (int i=1;i<=n;i++)
// printf("d[%d]=%I64d f[%d]=%I64d\n",i,d[i],i,f[i]);
// printf("\n");
}
printf("%I64d\n",f[n]);
}
int main()
{
freopen("landcraft.in","r",stdin);
freopen("landcraft.out","w",stdout);
init();
spfa();
}
換個方法，用dijstra考慮呢？
每次找當前能找到的最小值，用它來進行更新，遇到max就取max，遇到min就取min，有人會說，這肯定回wa完三。
其實不然。
我們這樣看，既然每次取得是最小值，那麼用來更新的一定是遞增的，所以對於一個點的限制只用考慮他最後一個max就夠了，然後再看這個點i的dis最大的前驅到這個點這一段，我們發現，他每次只會取min，而這些用來更新的點的dis已經大於了dis[i的最大的前驅]，所以取min不影響，所以總的來說，他就是個dijstra模型加一句帶限制的更新。
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
int n,m;
int tot=0;
int fir[200000],en[200000],nex[200000];
LL w[200000];
void ins(int a,int b,LL c){
nex[++tot]=fir[a];
fir[a]=tot;
en[tot]=b;
w[tot]=c;
}
int tot_=0;
int fir_[200000],en_[200000],nex_[200000];
void ins_(int a,int b){
nex_[++tot_]=fir_[a];
fir_[a]=tot_;
en_[tot_]=b;
}
LL dis[200000];
int rd[200000];
bool flag[200000];
int main(){
// freopen("landcraft.in","r",stdin);
// freopen("landcraft.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ins(a,b,c);
}
for (int i=1;i<=n;i++){
scanf("%d",&rd[i]);
for (int j=1;j<=rd[i];j++){
int x;
scanf("%d",&x);
ins_(x,i);
}
}
for (int i=0;i<=n;i++) dis[i]=99999999ll;
dis[1]=0;
for (int i=1;i<=n;i++){
int t=0;
for (int j=1;j<=n;j++)
if (!rd[j]&&flag[j]==false&&dis[j]
