#includebitsstdc++husing namespace std;inline static const nullptr_t _= ios_basesync_with_stdio0; cintienullptrcouttienullptr; return nullptr;;namespace fast_IO #define FASTIO #define I

这个代码的时间复杂度是O(n^3)，当n的值较大时，会导致超时。可以考虑使用Dijkstra算法对每个源点计算最短路径，来优化代码。

Dijkstra算法是一种贪心算法，用于解决单源最短路径问题。它的基本思想是从起点开始，每次选择一个距离起点最近的顶点，并更新与该顶点相邻的顶点的距离。重复这个过程，直到所有顶点都被遍历过。

下面是使用Dijkstra算法优化后的代码：

#include<bits/stdc++.h>
using namespace std;
inline static const nullptr_t _=[](){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    return nullptr;
}();
namespace fast_IO{
    #define FASTIO
    #define IOSIZE 100000
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #define getchar() cin.get()
    #define putchar(x) cout.put(x)
    #define isspace(ch)(ch<33)
    template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
    #ifdef _GLIBCXX_STRING
    inline bool read(string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
    #endif
    template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}using namespace fast_IO;
constexpr int INF=1e9;
int s1,t1,s2,t2,n,m;
int main() {
    io>>s1>>t1>>s2>>t2>>n>>m;
    vector<vector<int>> graph(n+1, vector<int>(n+1, INF));
    for(int i=1;i<=n;i++) graph[i][i]=0;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        graph[a][b]=c;
    }
    vector<int> dist1(n+1, INF);
    vector<int> dist2(n+1, INF);
    dist1[s1] = 0;
    dist2[s2] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq2;
    pq1.push({0, s1});
    pq2.push({0, s2});

    while(!pq1.empty()){
        int d = pq1.top().first;
        int u = pq1.top().second;
        pq1.pop();

        if(d > dist1[u]) continue;

        for(int v=1; v<=n; v++){
            if(dist1[v] > dist1[u] + graph[u][v]){
                dist1[v] = dist1[u] + graph[u][v];
                pq1.push({dist1[v], v});
            }
        }
    }

    while(!pq2.empty()){
        int d = pq2.top().first;
        int u = pq2.top().second;
        pq2.pop();

        if(d > dist2[u]) continue;

        for(int v=1; v<=n; v++){
            if(dist2[v] > dist2[u] + graph[u][v]){
                dist2[v] = dist2[u] + graph[u][v];
                pq2.push({dist2[v], v});
            }
        }
    }

    io<<dist1[t1]<<'\n';
    vector<int> path1;
    path1.emplace_back(t1);
    int cur = t1;
    while(cur != s1){
        for(int i=1; i<=n; i++){
            if(graph[i][cur] != INF && dist1[i] + graph[i][cur] == dist1[cur]){
                path1.emplace_back(i);
                cur = i;
                break;
            }
        }
    }
    reverse(path1.begin(), path1.end());
    for(int i=0; i<path1.size(); i++) io<<path1[i]<<' ';
    cout.put(10);

    io<<dist2[t2]<<'\n';
    vector<int> path2;
    path2.emplace_back(t2);
    cur = t2;
    while(cur != s2){
        for(int i=1; i<=n; i++){
            if(graph[i][cur] != INF && dist2[i] + graph[i][cur] == dist2[cur]){
                path2.emplace_back(i);
                cur = i;
                break;
            }
        }
    }
    reverse(path2.begin(), path2.end());
    for(int i=0; i<path2.size(); i++) io<<path2[i]<<' ';
    cout.put(10);
    return 0;
}

这个代码的时间复杂度是O(n^2logn)，可以通过所有测试用例