怎么做网贷网站,建自己的零售网站,建筑工程师培训学校,云南工程建设总承包公司网站我一直都不会dij的堆优化#xff0c;今天搞了一下。。。就是先弄一个优先队列#xff0c;存每个点的数据#xff0c;然后这个题就加了一点不一样的东西#xff0c;每次的最短路算两次#xff0c;一次是自己的最短路#xff0c;另一次是机关的最短路#xff0c;两者取最大…我一直都不会dij的堆优化今天搞了一下。。。就是先弄一个优先队列存每个点的数据然后这个题就加了一点不一样的东西每次的最短路算两次一次是自己的最短路另一次是机关的最短路两者取最大值才是该点的真正的最短路。 dij堆优化链接 题干 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 代码 #includeiostream
#includecstdio
#includecmath
#includectime
#includequeue
#includealgorithm
#includecstring
#includevector
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; ia[i].nxt){int j a[i].r;if(d1[j]g.disa[i].w){d1[j] g.dis a[i].w;if(!d[j]) qu.push((point){j,max(d1[j],d2[j])});}}for(int i1; ist[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
*/ 转载于:https://www.cnblogs.com/DukeLv/p/9532441.html
