#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 10000000;
int dis[501][501];
int cost[501][501];
int dest[501];
bool visited[501] = {false};
vector<int> paths[501];
int N,M,S,T;
void Dij(){
fill(dest,dest+501,INF);
dest[S] = 0;
for(int i=0; i<N; ++i){
int u = -1;
int mmin = INF;
for(int i=0; i<N; ++i){
if(!visited[i] && dest[i] < mmin){
u = i;
mmin = dest[i];
}
}
if(u==-1)
return;
visited[u] = true;
for(int v = 0; v < N; ++v){
if(!visited[v] && dis[u][v] != INF){
if(dest[u] + dis[u][v] < dest[v]){
dest[v] = dest[u] + dis[u][v];
paths[v].clear();
paths[v].push_back(u);
}else if(dest[u] + dis[u][v] == dest[v]){
paths[v].push_back(u);
}
}
}
}
}
vector<int> end_path;
vector<int> temp_path;
int end_cost = INF;
void DFS(int v){
temp_path.push_back(v);
if(v == S){
int temp_cost = 0;
for(int i = temp_path.size()-1; i>0; --i)
temp_cost += cost[temp_path[i]][temp_path[i-1]];
if(temp_cost < end_cost){
end_cost = temp_cost;
end_path = temp_path;
}
temp_path.pop_back();
return;
}
for(int i=0; i<paths[v].size(); ++i){
DFS(paths[v][i]);
}
temp_path.pop_back();
}
int main(){
cin>>N>>M>>S>>T;
for(int i = 0; i<N; ++i)
for(int j=0; j<N; ++j)
dis[i][j] = INF;
for(int i=0; i<M; ++i){
int s,e,d,c;
cin>>s>>e>>d>>c;
dis[s][e] = d;
dis[e][s] = d;
cost[s][e] = c;
cost[e][s] = c;
}
Dij();
DFS(T);
reverse(end_path.begin(),end_path.end());
for(auto v: end_path)
cout<<v<<" ";
cout<<dest[T]<<" "<<end_cost;
return 0;
}
Processed:
0.010, SQL:
9
