Pat 1030 travel plan (30 points) (unfinished)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,s,d;
int e[510][510],dis[510],cost[510][510];
vector<int>pre[510];
bool visit[510];
const int inf = 99999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v){
    
    temppath.push_back(v);
    if(v==s){
                                   // Traverse to the end , Calculation selection cost The smallest path 
        int tempcost=0;
        for(int i=temppath.size()-1;i>=0;i--){
    
            int id=temppath[i],nextid=temppath[i-1];
            tempcost+=cost[id][nextid];
        }
        if(tempcost<mincost){
                   // Update cost minimum path 
            mincost=tempcost;
            path=temppath;
        }
        temppath.pop_back();
        return;
    }
    for(int i=0;i<pre[v].size();i++)
        dfs(pre[v][i]);
    temppath.pop_back();                    // adopt v The path of point cannot be traversed s Recursively pop up the currently accessed node layer by layer v
}
int main() {
       
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &n, &m, &s, &d);
    for(int i=0;i<m;i++){
    
        int a,b;
        cin>>a>>b;
        scanf("%d",&e[a][b]);             //e[a][b] by a b Between dis
        e[b][a]=e[a][b];
        scanf("%d",&cost[a][b]);
        cost[a][b]=cost[b][a];
    }
    pre[s].push_back(s);
    dis[s]=0;
    //Dijksta, Each cycle  1. Find the shortest path from the current starting point to each point dis[u] 2. The update may be through u The shortest path to each point 
    for(int i=0;i<n;i++){
                      //Dijksta Record path pre Array , Determine the shortest path of one point at a time , Including self circulation n Time 
        int u=-1,minn=inf;
        for(int j = 0; j < n; j++) {
    
            if(visit[j] == false && dis[j] < minn) {
              // Traverse the current node to each point of the undetermined path dis[j] The shortest distance in , Among them to u The node distance is the shortest 
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;        // The shortest path to this point has been determined 
        for(int v=0;v<n;v++){
                                   // Update the starting point through u The current shortest distance from point to point , The first cycle updates the distance from the starting point to each point 
            if(visit[v]==false&&e[u][v]!=inf){
    
                if(dis[v]>dis[u]+e[u][v]){
                      // after u O 'clock v Is the distance between points closer 
                    dis[v]=dis[u]+e[u][v];                  
                    pre[v].clear();                         // If the path is updated , Clear the original path source ,v The previous node array in the shortest path of is pressed u node 
                    pre[v].push_back(u);
                }else if(dis[v]==dis[u]+e[u][v]){
               // The shortest path is not unique 
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(d);
    for(int i=path.size()-1;i>=0;i--)
        cout<<path[i]<<" ";
    cout<<dis[d]<<" "<<mincost;
    system("pause");
    return 0;
}