After writing this question today, I feel that the connection between theory and practice is not enough. I can think and code; From easy to difficult, start slowly ~

In fact, the code refers to the algorithm notes

This is an application of dijkstra algorithm; The point weight is added, and the edge weight should be an old friend, but the problem is that the topic requires the number of shortest paths and the maximum point weight. How to maintain these two values while the algorithm is running is something I haven't covered before. So I decided to learn this problem by example and read the analysis in the book.

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int inf=1000000; 
int main(void){
    int visited[501]={0};//City access array 
    int rescue[501]={0};//Number of rescue teams
    int dist[501]={0};//Shortest distance to each point 
    int edge[501][501]={0};
    int n,m,c1,c2;
    scanf("%d %d %d %d",&n,&m,&c1,&c2);
    for(int i=0;i<n;i++){
        scanf("%d",&rescue[i]);        
    }
    fill(edge[0],edge[0]+501*501,inf);//For initialization
    fill(dist,dist+501,inf);
    dist[c1]=0;
     
    for(int i=0;i<m;i++){//Structural map 
        int t1,t2,value;
        scanf("%d %d %d",&t1,&t2,&value);
        edge[t1][t2]=value;
        edge[t2][t1]=value;
    }

    int w[501]={0};
    int path_num[501]={0};
    w[c1]=rescue[c1];
    path_num[c1]=1;
    for(int i=0;i<n;i++){
        int minn=inf,minn_index=-1;
        for(int j=0;j<n;j++){
            if(minn>dist[j]&&visited[j]==0){
                minn=dist[j];    
                minn_index=j;
            }
        }
        if(minn_index==-1) break;
        visited[minn_index]=1;
        for(int j=0;j<n;j++){
            if(visited[j]==0&&edge[minn_index][j]!=inf){
                if(dist[j]>dist[minn_index]+edge[minn_index][j]){//If the current path is fuller than one circle, modify it 
                    dist[j]=dist[minn_index]+edge[minn_index][j];
                    w[j]=w[minn_index]+rescue[j];
                    path_num[j]=path_num[minn_index]; //cover path_num[j] 
                }
                else if(dist[j]==dist[minn_index]+edge[minn_index][j]){
                    path_num[j]=path_num[minn_index]+path_num[j];//The number of shortest paths has nothing to do with the point weight and is written outside 
                    if(w[j]<w[minn_index]+rescue[j]){ //If there are more rescue teams 
                        w[j]=w[minn_index]+rescue[j];//Inherit more rescue teams 
                    }
                }
            }
        }
    }
    

    printf("%d %d\n",path_num[c2],w[c2]);
    return 0;
}

 

Because I haven't touched the STL of c + + for a long time, I forgot many easy-to-use data structures in the past, so I can't think of it

Summarize what you learned today

Q1: difference between memset and fill

　　memset

1. Header file: #include < string h>
2. It is generally used to fill char arrays
3. If memset is used to fill the int array, only 0, - 1 and INF (0x3f3f3f3f) can be assigned. Otherwise, an error will occur and - 1 will be assigned directly

    fill

Header file: #include < algorithm >

Fill (start position, end, value) can be assigned arbitrarily

　　　fill(edge[0],edge[0]+501*501,inf); Assign a value to a two-dimensional array

 

Q2: I don't remember how to use vector So I read the document

To summarize the vector feature:

　　　　1.vector is an array that can be changed in size. The efficiency of accessing an element in the array is the same. However, changes in the size of the vector are handled automatically by the container

　　　　2. When a new element is inserted, the vector may need to request a new array and move all the elements, but the vector does not do this every time it is inserted.

　　　　3. In fact, vector keeps his hands on the above problems. Although it is said that it is growing dynamically, he will still apply for more space to deal with unexpected needs

　　　　4. The official suggestion is that the insertion needs to be carried out at the interval of exponential growth in order to share the time complexity? I don't quite understand

But when I see someone else's blog on the Internet, I compare vector insertion with list insertion; The former has better performance. The reason should be that the vector has a first-hand feature, which makes the insertion efficiency at the tail very high. However, each insertion of the list needs to apply for a new node, so the insertion efficiency of the vector is still very strong

However, the official documents say that if you insert or delete at a specific location, the vector is better than deque,list and forward_list difference

　　　　5. Compared with arrays, vector consumes more memory because of its effective storage management and dynamic growth

Create a new vector: vector < int > num [size]. < > It can also be a structure, which can be used for drawing collection and storage

Insert a new element at the tail: push_back()

empyt() checks whether the vector is empty

capacity() returns the actual allocated size of the vector

　　shrink_ to_ Fit () is only supported by C + + 11, which is to make capacity and size the same

Let's look at the official documents. You can only remember language related things if you use them all the time, otherwise you will forget them quickly, but since you have learned it, it's faster to pick it up again than to start from scratch!