Pro5_TLE_0

原始文件为 CPP 代码，本文是转换后的 Markdown 文件。

#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;

const int INF = 100000000;
const int maxn = 1005;
int type[maxn];
int d[maxn][maxn];

int main()
{
    freopen("in.txt","r",stdin);
    int n,m,k; scanf("%d%d%d",&n,&m,&k);

    for (int i = 0; i < n; ++i)
        scanf("%d",&type[i]);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            d[i][j] = INF;

        d[i][i] = 0;
    }

    for (int i = 0; i < m; ++i)
    {
        int from,to,weight;
        scanf("%d%d%d",&from,&to,&weight);
        d[from-1][to-1] = weight;
        d[to-1][from-1] = weight;
    }

    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    multimap<int,int> temp;

    for (int i = 0; i < n; ++i)
    {
        int ans = 0;
        int count = 0;

        temp.clear();
        for (int j = 0; j < n; ++j)
            temp.insert(make_pair(d[i][j],j));

        // sort(temp.begin(),temp.end());

        for (auto& x : temp)
        {
            if (type[x.second] == 1 && x.first < INF)
            {
                ans += x.first;
                if (++count == k)   break;
            }
        }
        cout << ans << endl;

    }
}