首页 > 编程语言 >第九届福建省大学生程序设计竞赛-重现赛(感谢承办泉州师范学院) spfa变形

第九届福建省大学生程序设计竞赛-重现赛(感谢承办泉州师范学院) spfa变形

时间:2023-04-24 22:39:54浏览次数:47  
标签:node 第九届 师范学院 int there Xzz ai spfa include


Xzz is a child with severe procrastinations. The new semester begins, He still has a lot of homework to do. Now, he needs your help. As the best friend, you are good at math. So, you will help him do some math homework. Now Xzz wants to go to your home. You can regard the traffic network as a undirected graph with n nodes (numbered from 1 to n) and m edges.

Xzz’s home at node s, and your at node t. At each node i, there is a traffic light, and the traffic light change the status after ai, which means that you can only leave node i, at time[0, ai), [2 * ai, 3 * ai), [4 * ai, 5 * ai), … , [2k * ai, (2 * k + 1) * ai). If ai = 0 means there is no traffic light, you can leave at any time. And there are m edges, each edge means it will take Xzz vi time from node xi to node yi. Now Xzz wants to know how much time he will take to arrive your home.

Input
First line of the input file contains an integer T(0 < ≤ 20) that indicates how many cases of inputs are there.

The description of each case is given below:

The first line of each case contains two numbers n, m, means there are n nodes and m edges.

(n ≤ 1000, m ≤ n(n-1) / 2)

Then follow n lines. In ith line there will be a number, ai.(ai ≤ 1000)

Then follow m lines. In ith line there will be three numbers, xi, yi and vi, means there is a edge between xi and yi, and Xzz take vi time to go trough this edge. vi ≤ 1000.

The last line contains two numbers s, t. It’s guarantee that there is at least one path between node s and t.

Output
One integer means the minimum time Xzz go to node t.
Sample Input
1
9 14
3
5
7
3
5
7
9
3
5
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 9 6
7 8 1
8 9 7
1 5
Sample Output
28

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<set>
using namespace std;
#define maxn 1000005
#define inf 0x3f3f3f3f
int a[maxn];
struct edge
{
    int from,to,w,next;
 }e[maxn];
 int head[maxn],vis[maxn],dist[maxn];
 int n,m ,t;
 void add(int i,int j,int w)
 {
    e[t].from=i;
    e[t].to=j;
    e[t].w=w;
    e[t].next=head[i];
    head[i]=t++;
  }

  void spfa(int s)
  {
    queue<int> q;
    for(int i=1;i<=n;i++){
        dist[i]=inf;
      }
      memset(vis,false,sizeof(vis));
      q.push(s);
      dist[s]=0;
      while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=false;
        int x=dist[u]/a[u];
        int noww=dist[u];
        if(x%2==1)noww=(x+1)*a[u];
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(dist[v]>noww+e[i].w){
                dist[v]=noww+e[i].w;
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                  }
              }
          }
      }
  }


int main()
{
    int T;cin>>T;
    while(T--){
    scanf("%d%d",&n,&m);
    t=0;
    memset(head,-1,sizeof(head));
    memset(a,0,sizeof(a));
    memset(e,0,sizeof(e));
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--){
        int s,t,w;
        scanf("%d%d%d",&s,&t,&w);
        add(s,t,w);
        add(t,s,w);
    }
    int start,ed;
    scanf("%d%d",&start,&ed);
    spfa(start);
    cout<<dist[ed]<<endl;
    }
}


标签:node,第九届,师范学院,int,there,Xzz,ai,spfa,include
From: https://blog.51cto.com/u_15657999/6221923

相关文章

  • ACM International Collegiate Programming Contest 2014 B SPFA 统计路径
    FloweryTrails!”()”*+,-).%”/)’0”122”1!2”342”522”!22”652”!42”72”72”5!2”!12”622”18!”162”!12”6”7”4”9”3”5”8”1”2”Inordertoattractmorevisitors,themanagerofanationalp......
  • 图的最短路问题(综合详解!!!看这一篇就够了)(spfa-Dijkstra-floyd-模板代码c-)
    文章目录图论:三种最短路及模板模板SPFA算法Floyd算法Dijkstra算法例题与应用反向建边最短路计数1488.最短距离3305.作物杂交4074.铁路与公路图论:三种最短路及模板注意:在这三种算法中我均使用的链式前向星存图,具体方式请看我这篇博客:链式前向星存图详解模板SPFA算法spfa是优化......
  • Codeforces Round #257 (Div. 1)B题Jzzhu and Cities(spfa+slf优化)
    题目地址:http://codeforces.com/contest/450/problem/D这题有重边,需要去重。。sad。当时居然没看见。。这题只要引入一个最短路条数,然后再遍历火车线,如果最短路与火车线长度相等,此时如果最短路条数是1的话,那说明这个最短路就是火车线,不能去掉,如果最短路条数大于1条,说明除了这条火车......
  • spfa求最短路——BFS,数组实现邻接表,数组实现队列
    题目描述题目来源AcWing给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。数据保证不存在负权回路。输入格式第一行包含整数n和m。接下来m行每行包含三个......
  • 2018年第九届蓝桥杯—B组C/C++程序设计省赛解题-2明码
    .明码汉字的字形存在于字库中,即便在今天,16点阵的字库也仍然使用广泛。16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。一个字节可以存储8位信息,用32个字节就可以存一个汉字的字形了。把每个字节转为2进制表示,1表示墨迹,0表示底色。每行2个字节,一共16......
  • 【模板】逆单源最短(反向建图) + spfa
    题目要求:不仅要求单源最短路径,还要求其余点到该点的最短路径做法:建立反图求逆单源最短路径,至于单源最短路径选择合适于题目即可参考题目1#include<iostream>2#include<queue>3#include<cstring>45usingnamespacestd;67typedeflonglongLL;8typ......
  • 5098: Sweet Butter spfa
    描述  FarmerJohnhasdiscoveredthesecrettomakingthesweetestbutterinallofWisconsin:sugar.Byplacingasugarcubeoutinthepastures,heknowstheN(1<=N<=500)cowswilllickitandthuswillproducesuper-sweetbutterwhichcan......
  • 最小费用最大流( spfa )
     constintN=5005,M=1e5+100;#defineinf1e9intall=1,hd[N],go[M],w[M],nxt[M],cost[M];intS,T,n,m;intpre[N],mn[N],dis[N],vis[N],ans=0;void......
  • SPFA
    importjava.util.Arrays;importjava.util.LinkedList;importjava.util.Queue;publicclassSPFA{ publicstaticvoidmain(String[]args){ } //边存......
  • Bellman_ford和spfa算法
    Bellman_ford算法bellman_ford算法在要求起点到终点存在负权边,要求在指定k步(这是spfa无法替代的)bellman_ford和spfa都可以判断图中有无负权环......