ZOJ 3946 Highway Project

Description

n个点（0~n）m条边，两个权值

多开一个cs[N]数组，存到某点所选择的那条边（题目给出）的花费权值

题目链接

这题改了一晚上最后发现：dis[N]数组按n的大小(i = 0; i <= n; ++i)标INF就WA，整个memset就AC, 为啥啊？！

Code of spfa

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100005;

int n, m;
int cnt;
struct edge
{
    int to, d, c, pre;
} a[N << 1];

bool vis[N];
int head[N], cs[N], tot, sum;
long long dis[N];
deque<int> q;

void add(int from, int to, int d, int c)
{
    a[cnt].to = to;
    a[cnt].d = d;
    a[cnt].c = c;
    a[cnt].pre = head[from];
    head[from] = cnt++;
}

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
    {
        vis[i] = 0;
        head[i] = -1;
//        dis[i] = INF;
        cs[i] = INF;
    }
    memset(dis, INF, sizeof(dis));
}

void update(int t)
{
    if(!vis[t])
    {
        vis[t] = 1;
        if(q.empty() || dis[q.front()] < dis[t] || dis[t] * tot >= sum)
            q.push_back(t);
        else
            q.push_front(t);
        sum += dis[t];
        tot++;
    }
}

void spfa(int start)
{
    dis[start] = 0;
    cs[0] = 0;
    q.clear();
    q.push_front(start);
    vis[start] = 1;
    tot = 1, sum = 0;

    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        sum -= dis[first];
        tot--;

        for(int i = head[first]; ~i; i = a[i].pre)
        {
            int t = a[i].to;
            if(dis[t] > dis[first] + a[i].d)
            {
                dis[t] = dis[first] + a[i].d;
                cs[t] = a[i].c;
                update(t);
            }
            if(dis[t] == dis[first] + a[i].d && cs[t] > a[i].c)
            {
                cs[t] = a[i].c;
                update(t);
            }
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        init();
        int from, to, times, cost;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d%d", &from, &to, &times, &cost);
            add(from, to, times, cost);
            add(to, from, times, cost);
        }
        spfa(0);
        long long ans_d = 0;
        long long ans_c = 0;
        for(int i = 0; i < n; ++i)
        {
            ans_d += dis[i];
            ans_c += cs[i];
        }
        cout << ans_d << ' ' << ans_c << '\n';
    }
    return 0;
}

Dijkstra（TLE）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100005;

int n, m;
int cnt;
struct edge
{
    int to, d, c, pre;
} a[N << 1];

bool vis[N];
int head[N], cs[N];
long long dis[N];

void add(int from, int to, int d, int c)
{
    a[cnt].to = to;
    a[cnt].d = d;
    a[cnt].c = c;
    a[cnt].pre = head[from];
    head[from] = cnt++;
}

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
    {
        vis[i] = 0;
        head[i] = -1;
        dis[i] = INF;
        cs[i] = INF;
    }
}

void Dijkstra(int start)
{
    dis[start] = 0;
    cs[start] = 0;
    int pos = start;
    int mmin;
    while(pos != -1)
    {
        for(int i = head[pos]; ~i; i = a[i].pre)
        {
            if(vis[ a[i].to ])
                continue;
            if(dis[ a[i].to ] == INF || dis[ a[i].to ] > dis[pos] + a[i].d)
            {
                dis[ a[i].to ] = dis[pos] + a[i].d;
                cs[ a[i].to ] = a[i].c;
            }
            if(dis[ a[i].to ] == dis[pos] + a[i].d)///时间相等看花费
                cs[ a[i].to ] = min(cs[ a[i].to ], a[i].c);
        }
        vis[pos] = 1;

        pos = -1;
        mmin = -1;
        for(int i = 0; i < n; ++i)
            if(!vis[i] && dis[i] != INF && (mmin == -1 || mmin > dis[i]))
            {
                mmin = dis[i];
                pos = i;
            }
    }
    return ;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        init();
        int from, to, times, cost;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d%d", &from, &to, &times, &cost);
            add(from, to, times, cost);
            add(to, from, times, cost);
        }
        Dijkstra(0);
        long long ans_d = 0;
        long long ans_c = 0;
        for(int i = 0; i < n; ++i)
        {
            ans_d += dis[i];
            ans_c += cs[i];
        }
        cout << ans_d << ' ' << ans_c << '\n';
    }
    return 0;
}