Submission #1261561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261561		phtung	Price List (POI13_cen)	C++20	30 / 100	326 ms	8012 KiB

cen

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int inf = 1e9 + 7; 
const int maxn = 1e5 + 5;
int n, m, k, a, b; 
vector<pair<int,int>> adj[maxn];

void sub1()
{
    vector<vector<int>> min_dist(n + 1, vector<int>(n + 1, inf));

    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v; 
        min_dist[u][v] = 1;
        min_dist[v][u] = 1;
        adj[u].push_back({v, a}); 
        adj[v].push_back({u, a}); 
    }

    for(int i = 1; i <= n; i++) min_dist[i][i] = 0; 

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                min_dist[i][j] = min(min_dist[i][j], min_dist[i][k] + min_dist[k][j]); 
            }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            if(min_dist[i][j] == 2)
            {
                adj[i].push_back({j, b});
                adj[j].push_back({i, b}); 
            }
        }
    }

    vector<int> dist(n + 1, inf), vis(n + 1, 0);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; 

    pq.push({0, k});
    dist[k] = 0; 

    while(!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();

        if(vis[u]) continue;
        vis[u] = 1;

        for(auto [v, w] : adj[u])
        {
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w; 
                pq.push({dist[v], v}); 
            }
        }
    }

    for(int i = 1; i <= n; i++) cout << dist[i] << "\n";    

}

void solve()
{
    cin >> n >> m >> k >> a >> b; 

    if(n <= 700) sub1(); 
}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

cen.cpp: In function 'int main()':
cen.cpp:91:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cen.cpp:92:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10