我一直都不會(huì)dij的堆優(yōu)化，今天搞了一下。。。就是先弄一個(gè)優(yōu)先隊(duì)列，存每個(gè)點(diǎn)的數(shù)據(jù)，然后這個(gè)題就加了一點(diǎn)不一樣的東西，每次的最短路算兩次，一次是自己的最短路，另一次是機(jī)關(guān)的最短路，兩者取最大值才是該點(diǎn)的真正的最短路。

dij堆優(yōu)化鏈接

題干：

Description 在一個(gè)遙遠(yuǎn)的世界里有兩個(gè)國(guó)家：位于大陸西端的杰森國(guó)和位于大陸東端的 克里斯國(guó)。兩個(gè)國(guó)家的人民分別信仰兩個(gè)對(duì)立的神：杰森國(guó)信仰象征黑暗和毀滅 的神曾·布拉澤，而克里斯國(guó)信仰象征光明和永恒的神斯普林·布拉澤。 幻想歷 8012年 1月，杰森國(guó)正式宣布曾·布拉澤是他們唯一信仰的神，同 時(shí)開(kāi)始迫害在杰森國(guó)的信仰斯普林·布拉澤的克里斯國(guó)教徒。 幻想歷 8012年 3月2日，位于杰森國(guó)東部小鎮(zhèn)神諭鎮(zhèn)的克里斯國(guó)教徒發(fā)動(dòng) 起義。 幻想歷 8012年 3月7日，神諭鎮(zhèn)的起義被杰森國(guó)大軍以殘酷手段鎮(zhèn)壓。 幻想歷 8012年 3月8日，克里斯國(guó)對(duì)杰森國(guó)宣戰(zhàn)。由數(shù)十萬(wàn)大軍組成的克 里斯軍團(tuán)開(kāi)至兩國(guó)邊境，與杰森軍團(tuán)對(duì)峙。 幻想歷 8012年 4月，克里斯軍團(tuán)攻破杰森軍團(tuán)防線進(jìn)入神諭鎮(zhèn)，該鎮(zhèn)幸存 的克里斯國(guó)教徒得到解放。 戰(zhàn)爭(zhēng)隨后進(jìn)入膠著狀態(tài)，曠日持久。戰(zhàn)況慘烈，一時(shí)間槍林彈雨，硝煙彌漫， 民不聊生。 幻想歷 8012年 5月12日深夜，斯普林·布拉澤降下神諭：“Trust me, earn eternal life.”克里斯軍團(tuán)士氣大增。作為克里斯軍團(tuán)的主帥，你決定利用這一機(jī) 會(huì)發(fā)動(dòng)奇襲，一舉擊敗杰森國(guó)。具體地說(shuō)，杰森國(guó)有 N 個(gè)城市，由 M條單向道 路連接。神諭鎮(zhèn)是城市 1而杰森國(guó)的首都是城市 N。你只需摧毀位于杰森國(guó)首都 的曾·布拉澤大神殿，杰森國(guó)的信仰，軍隊(duì)還有一切就都會(huì)土崩瓦解，灰飛煙滅。 為了盡量減小己方的消耗，你決定使用自爆機(jī)器人完成這一任務(wù)。唯一的困 難是，杰森國(guó)的一部分城市有結(jié)界保護(hù)，不破壞掉結(jié)界就無(wú)法進(jìn)入城市。而每個(gè) 城市的結(jié)界都是由分布在其他城市中的一些結(jié)界發(fā)生器維持的，如果想進(jìn)入某個(gè) 城市，你就必須破壞掉維持這個(gè)城市結(jié)界的所有結(jié)界發(fā)生器。 現(xiàn)在你有無(wú)限多的自爆機(jī)器人，一旦進(jìn)入了某個(gè)城市，自爆機(jī)器人可以瞬間 引爆，破壞一個(gè)目標(biāo)（結(jié)界發(fā)生器，或是杰森國(guó)大神殿），當(dāng)然機(jī)器人本身也會(huì) 一起被破壞。你需要知道：摧毀杰森國(guó)所需的最短時(shí)間。 Input 第一行兩個(gè)正整數(shù) N, M。 接下來(lái) M行，每行三個(gè)正整數(shù) ui, vi, wi，表示有一條從城市ui到城市 vi的單 向道路，自爆機(jī)器人通過(guò)這條道路需要 wi的時(shí)間。 之后 N 行，每行描述一個(gè)城市。首先是一個(gè)正整數(shù) li，維持這個(gè)城市結(jié)界所 使用的結(jié)界發(fā)生器數(shù)目。之后li個(gè)1~N 之間的城市編號(hào)，表示每個(gè)結(jié)界發(fā)生器的 位置。如果 Li = 0，則說(shuō)明該城市沒(méi)有結(jié)界保護(hù)，保證L1 = 0 。 Output 僅包含一個(gè)正整數(shù) ，擊敗杰森國(guó)所需的最短時(shí)間。 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

代碼：

#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> #include<vector> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) {char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-') op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op) x = -x; } template <class T> void write(T x) {if(x < 0) putchar('-'), x = -x;if(x >= 10) write(x / 10);putchar('0' + x % 10); } struct node {int l,r,nxt,w;bool operator < (const node &other) const{return w < other.w;} } a[70005]; struct point {int x,dis;bool operator < (const point &other) const{return (other.dis < dis) || (x < other.x && dis == other.dis);} }; int len = 0,last[3005],m,n; int vis[3005]; int d1[3005],d2[3005],d[3005]; int st[3005][3005]; priority_queue <point> qu; void add(int x,int y,int w) {a[++len].l = x;a[len].r = y;a[len].w = w;a[len].nxt = last[x];last[x] = len; } void dij() {vis[1] = 0;d1[1] = 0;qu.push((point){1,max(d1[1],d2[1])});while(!qu.empty()){point g = qu.top();qu.pop();if(vis[g.x])continue;if(g.dis != max(d1[g.x],d2[g.x]))continue;for(int i = last[g.x]; i; i=a[i].nxt){int j = a[i].r;if(d1[j]>g.dis+a[i].w){d1[j] = g.dis + a[i].w;if(!d[j]) qu.push((point){j,max(d1[j],d2[j])});}}for(int i=1; i<=st[g.x][0]; ++i){d[st[g.x][i]]--;if(!d[st[g.x][i]]){d2[st[g.x][i]]=g.dis;qu.push((point){st[g.x][i],max(d1[st[g.x][i]],d2[st[g.x][i]])});}}vis[g.x] = 1; } } int main() {read(n);read(m);duke(i,1,m){int x,y,w;read(x);read(y);read(w);add(x,y,w);}memset(d1,127,sizeof(d1));duke(i,1,n){int p;read(d[i]);duke(j,1,d[i]){read(p);st[p][++st[p][0]] = i;}}dij();printf("%d\n",max(d1[n],d2[n]));return 0; } /* 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 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/DukeLv/p/9532441.html

總結(jié)

以上是生活随笔為你收集整理的B1922 [Sdoi2010]大陆争霸 最短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。