做网站哪种字体好看,自己做的网站不备案不能访问吗,wordpress 3.9.2 下载,网站色调红黑题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/1080/D 来源#xff1a;牛客网
这天#xff0c;tokitsukaze带着她的舰队去才归一儿海探索。这个海域有n个站点#xff0c;深海舰队控制着这片海域的m条航线#xff0c;这些航线连接着这n个点
链接https://ac.nowcoder.com/acm/contest/1080/D 来源牛客网
这天tokitsukaze带着她的舰队去才归一儿海探索。这个海域有n个站点深海舰队控制着这片海域的m条航线这些航线连接着这n个点第i条航线连接着uivi两个点。航线都是正确的也就是说没有重复的航线也没有任何一个点与自己相连。tokitsukaze的舰队经过第i条航线时会受到来自深海舰队的ai点伤害。 tokitsukaze可以在某个休息站点将接下来的战斗切换至夜战模式这样在她的舰队经过第i条航线时受到的伤害就变为bi不过一旦切换到夜战模式就不能再次切换回来所以她必须考虑清楚在哪里切换。 现在有个限时活动。活动难度分为1,2,3,4,...n在难度1下tokitsukaze可以在任意站点切换到夜战模式而在难度2下不能在站点1切换到夜战模式在难度3下不能在站点1,2切换模式...以此类推即在难度k下tokitsukaze不能在站点1,2,3,4,5...k-1切换模式。同时活动还要求在游戏结束时必须处于夜战模式。 现在tokitsukaze的舰队从s点出发要前往深海大本营所在的t点。请你告诉她在难度为1,2,3,4,5...n时她的舰队结束游戏时受到的最小伤害。
输入描述:
第一行包括2个正整数nm(2≤n≤10^51≤m≤min(n*(n-1)/2,10^5))。
接下来m行每行包括4个正整数uvab(1≤u,v≤n1≤a,b≤10^9)。
最后一行包括2个正整数st(1≤s,t≤n)。
输出描述:
请你告诉tokitsukaze在难度为1,2,3,4,5...n时她的舰队处于夜战模式结束游戏受到的最小伤害。
示例1
输入
复制
4 3
1 4 1 30
1 2 1 10
1 3 20 1
2 3输出
复制
2
11
21
33说明
活动难度为1时在编号为1的点切换模式受到的最小伤害为2。
活动难度为2时在编号为2的点切换模式受到的最小伤害为11。
活动难度为3时在编号为3的点切换模式受到的最小伤害为21。
活动难度为4时在编号为4的点切换模式受到的最小伤害为33。
示例2
输入
复制
4 3
1 4 30 1
1 2 10 1
1 3 20 1
3 1输出
复制
1
1
1
51说明
活动难度为1时在编号为3的点切换模式受到的最小伤害为1。
活动难度为2时在编号为3的点切换模式受到的最小伤害为1。
活动难度为3时在编号为3的点切换模式受到的最小伤害为1。
活动难度为4时在编号为4的点切换模式受到的最小伤害为51。路线是3-1-4-1。因为必须处于夜战模式结束游戏所以在到达1后还要拐去4去切换模式。解题报告 因为有点懒而且比较水所以直接改改官方题解。 s为起点用边权a跑一遍最短路记为disa。 把边的方向反转t为起点用边权b跑一遍最短路记为disb。但是这题是双向边所以并不用反转 那么在节点 i 切换模式的最小伤害为disaidisbi再做一遍后缀min即可。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
struct Edge {int v,ne;ll a,b;
} e[MAX];
struct Point {int u;ll c;Point(){}Point(int u,ll c):u(u),c(c){}bool operator(const Point b) const {return c b.c;}
};
int tot,head[MAX];
void add(int u,int v,ll a,ll b) {e[tot].v v;e[tot].a a;e[tot].b b;e[tot].ne head[u];head[u] tot;
}
ll disa[MAX],disb[MAX];
bool vis[MAX];
void Dija(int st,int ed) {memset(disa,0x3f,sizeof disa);memset(vis,0,sizeof vis);priority_queuePoint pq;pq.push(Point(st,0));
// vis[st] 1;disa[st] 0;while(!pq.empty()) {Point cur pq.top();pq.pop();if(vis[cur.u] 1) continue;vis[cur.u] 1;for(int i head[cur.u]; ~i; i e[i].ne) {int v e[i].v;if(vis[v] || disa[v] disa[cur.u] e[i].a) continue;disa[v] disa[cur.u] e[i].a;pq.push(Point(v,disa[v]));}}
}
void Dijb(int st,int ed) {memset(disb,0x3f,sizeof disb);memset(vis,0,sizeof vis);priority_queuePoint pq;pq.push(Point(st,0));
// vis[st] 1;disb[st] 0;while(!pq.empty()) {Point cur pq.top();pq.pop();if(vis[cur.u] 1) continue;vis[cur.u] 1;for(int i head[cur.u]; ~i; i e[i].ne) {int v e[i].v;if(vis[v] || disb[v] disb[cur.u] e[i].b) continue;disb[v] disb[cur.u] e[i].b;pq.push(Point(v,disb[v]));}}
}
ll ans[MAX];
int main()
{int n,m,st,ed;memset(head,-1,sizeof head);cinnm;for(int a,b,c,d,i 1; im; i) {scanf(%d%d%d%d,a,b,c,d);add(a,b,c,d);add(b,a,c,d);}scanf(%d%d,st,ed);Dija(st,ed);Dijb(ed,st);ans[n] disa[n]disb[n];for(int i n-1; i1; i--) {ans[i] min(ans[i1],disa[i]disb[i]);}for(int i 1; in; i) printf(%lld\n,ans[i]);return 0 ;
}