最短路多条路径

╰+哭是因爲堅強的太久メ 2022-06-16 06:13 215阅读 0赞

#include<cstdio>
    #include<iostream>
    #include<queue>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<vector>
    #include<fstream>
    
    using namespace std;
    const int maxn = 900+10;
    const int inf = 0x3f3f3f3f;
    
    int p[maxn];
    int head[maxn];
    int vis[maxn];
    int N,M,L,K,S,T;
    int map[maxn][maxn];
    int dis[maxn];
    vector<int>path[maxn*(maxn-1)/2];
    
    struct node {
        int t, c;
        int next;
        node() {
        }
        node (int _t, int _c, int _ne) {
            t = _t;
            c = _c;
            next = _ne;
        }
    }edge[maxn*(maxn-1)/2];
    
    int cnt = 0;
    void add(int u, int v, int c) {
        edge[cnt].t = v;
        edge[cnt].c = c;
        edge[cnt].next = head[u];
        head[u] = cnt;
        cnt++;
    }
    
    typedef pair<int, int> P;
    vector<int>pa[maxn*(maxn-1)/2];
    
    void bfs(int s) {
        queue<P>q;
        q.push(make_pair(s, 0));
        double d = 1.0/(L*1.0);
        p[s] += p[s];
        vis[s] = 1;
        while (!q.empty()) {
            P now = q.front();
            q.pop();
            int u = now.first;
            int c = now.second;
    
            for (int i=head[u]; i!=-1; i=edge[i].next) {
                int v = edge[i].t;
    
                if (!vis[v] && c+1 < L)
                    q.push(make_pair(v, c+1)), vis[v]=1, p[v]+=ceil(p[v]*(1-d*(c+1)));
    
            }
        }
    }
    
    void Dijkstra(int n, int v, int *dist, vector<int> *prev, int c[maxn][maxn])
    {
        bool s[maxn];    // 判断是否已存入该点到S集合中
        for(int i=0; i<n; ++i)
        {
            dist[i] = c[v][i];
            s[i] = 0;     // 初始都未用过该点
            if(dist[i] < inf)
                prev[i].push_back(v);
        }
        dist[v] = 0;
        s[v] = 1;
        for(int i=2; i<=n; ++i)
        {
            int tmp = inf;
            int u = v;
            // 找出当前未使用的点j的dist[j]最小值
            for(int j=0; j<n; ++j)
                if((!s[j]) && dist[j]<tmp)
                {
                    u = j;              // u保存当前邻接点中距离最小的点的号码
                    tmp = dist[j];
                }
            s[u] = 1;    // 表示u点已存入S集合中
            // 更新dist
            for(int j=0; j<n; ++j)
                if((!s[j]) && c[u][j]<inf)
                {
                    int newdist = dist[u] + c[u][j];
                    if(newdist <= dist[j])
                    {
                        if (newdist < dist[j]) {
                            prev[j].clear();
                            dist[j] = newdist;
                        }
                        prev[j].push_back(u);
                    }
                }
        }
    }
    
    int pcnt = 0;
    void searchPath(vector<int> *prev, int v, int u, int sta[], int len) {
        if (u == v) {
            pcnt++;
            pa[pcnt].push_back(S);
            return ;
        }
        sta[len] = u;
        for (int i = 0 ; i < prev[u].size(); ++i ) {
            if (i > 0) {
                for (int j = len - 1  ; j >= 0 ; --j) {
                    pa[pcnt].push_back(sta[j]);
                }
            }
            searchPath(prev, v, prev[u][i], sta, len + 1);
            pa[pcnt].push_back(u);
        }
    }
    
    int main() {
    //    ifstream in("/Volumes/DATA/mine/0000/0000/9.txt");
        cnt = 0;
        memset(head, -1, sizeof(head));
        for (int i=0; i<N; i++)
            path[i].clear(), pa[i].clear();
        memset(map, inf, sizeof(map));
        memset(vis, 0, sizeof(vis));
        scanf("%d%d%d%d%d%d", &N, &M, &L, &K, &S, &T);
    
        for (int i=0; i<N; i++)
            scanf("%d", &p[i]);
    //        in>>p[i];
    
        for (int i=0; i<M; i++) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
    //        in>>u>>v>>c;
            if (map[u][v] != inf)
                cout<<"map"<<endl;
            add(u, v, c);
            add(v, u, c);
            map[u][v]=map[v][u]=c;
        }
        bfs(S);
    
        Dijkstra(N, S, dis, path, map);
        int sta[maxn];
        pcnt = 0;
        pa[pcnt].push_back(S);
    
        searchPath(path, S, T, sta, 0);
        int ans = 0, res=inf, pos=-1;
        for (int i=1; i<=pcnt; i++){
            int asum = 0, rsum = 0;
            for (int j=0; j<pa[i].size(); j++)
                asum += p[pa[i][j]], asum %= K;
            int nn = 0;
            if (pa[i].size()%2 == 0)
                nn = (int)pa[i].size()/2;
            else
                nn = (int)pa[i].size()/2+1;
            for (int j=nn; j<pa[i].size(); j++)
                rsum += p[pa[i][j]];
    
            if (asum > ans) {
                ans = asum;
                res = rsum;
                pos = i;
            }
            else if (asum == ans && rsum < res){
                ans = asum;
                res = rsum;
                pos = i;
            }
        }
    
        if (dis[T] >= inf)
            puts("-1");
        else {
            printf("%d %d %d %d\n", pcnt, dis[T], ans, res);
            for (int i=0; i<pa[pos].size(); i++)
                if (i == 0)
                    printf("%d", pa[pos][i]);
                else
                    printf("->%d", pa[pos][i]);
            printf("\n");
        }
    
        return 0;
    }