HDOJ3790——双关键字最短路

Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)

Output

输出 一行有两个数， 最短距离及其花费。

注意如果最短距离有多条路线，则输出花费最少的。所以这道题有两个关键字，一个是距离，一个是花费。其中距离优先。
所以在更新状态的时候，如果距离相等，要记录花费较少的。

/*Dijkstra模板题*/
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x7fffffff;
const int inf = 0x3f3f3f3f;
int n,m,mat[1005][1005],cost[1005][1005];
int d[1001],c[1001],vis[1001];
void dijkstra(int s,int t)
{
  for(int i=1;i<=n;i++)   //初始化
  {
    d[i] = INF;
    c[i] = INF;
    vis[i] = 0;
  }
  c[s] = 0;
  d[s] = 0;
  while(true)
  {
    int minn = INF;
    int node = -1;
    for(int i=1;i<=n;i++)
    {
      if(!vis[i] && d[i] < minn)
      {
        node = i;
        minn = d[i];
      }
    }
    if(node == -1)  break;
    vis[node] = 1;
    for(int i=1;i<=n;i++)
    {
      if(vis[i] != 1 && mat[node][i] != inf)
      {
        if((mat[node][i] + d[node]) < d[i])
        {
          d[i] = mat[node][i] + d[node];
          c[i] = cost[node][i] + c[node];
        }
        else if((mat[node][i] + d[node]) == d[i])  //如果距离相等，更新花费小的
        {
          if((cost[node][i] + c[node]) < c[i])
            c[i] = cost[node][i] + c[node];
        }
      }
    }
  }
  cout << d[t] << " " << c[t] << endl;
}

int main()
{
  ios::sync_with_stdio(false);
  int a,b,d,p,s,t;
  while(cin>>n>>m && (n && m))
  {
    memset(mat,inf,sizeof(mat));
    memset(cost,inf,sizeof(mat));
    for(int i=0;i<m;i++)
    {
      cin >> a >> b >> d >> p;
      if(mat[a][b] > d)
      {
        mat[a][b] = mat[b][a] = d;
        cost[a][b] = cost[b][a] = p;
      }
      else if(mat[a][b] == d)
      {
        if(cost[a][b] > p)  cost[a][b] = cost[b][a] = p;
      }
    }
    cin >> s >> t;
    dijkstra(s,t);
  }
}

SPFA解法

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int inf = 0x3f3f3f3f;
int vis[1024],d[1024],c[1024],enqueue_num[1024];
int n,m,s,t;
struct Node
{
  int id;
  int dis;
  int c;
  Node(int id,int dis,int c):id(id),dis(dis),c(c){};
};
vector<Node> mat[1024];
bool SPFA()
{
  queue<int> q;
  for(int i=0;i<=n;i++)
  {
    d[i] = inf;
    c[i] = inf;
    enqueue_num[i] = vis[i] = 0;
  }
  d[s] = c[s] = 0;
  vis[s] = 1;
  q.push(s);
  while(!q.empty())
  {
    int f = q.front();q.pop();
    vis[f] = 0;
    int len = mat[f].size();
    for(int i=0;i<len;i++)
    {
      Node now = mat[f][i];
      if(d[now.id] > now.dis + d[f])
      {
        d[now.id] = now.dis + d[f];
        c[now.id] = now.c + c[f];
        if(!vis[now.id])
        {
          q.push(now.id);
          enqueue_num[now.id]++;
          if(enqueue_num[now.id] >= n)  return false;
          vis[now.id] = 1;
        }
      }
      else if(d[now.id] == now.dis + d[f])
      {
        if(c[now.id] > now.c + c[f])
        {
          c[now.id] = now.c + c[f];
          if(!vis[now.id])
          {
            q.push(now.id);
            enqueue_num[now.id]++;
            if(enqueue_num[now.id] >= n)  return false;
            vis[now.id] = 1;
          }
        }
      }
    }
  }
  return true;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,dis,p;
  while(cin >> n >> m && (n && m))
  {
    for(int i=0;i<1024;i++) mat[i].clear();
    for(int i=1;i<=m;i++)
    {
      cin >> a >> b >> dis >> p;
      mat[a].push_back(Node(b,dis,p));
      mat[b].push_back(Node(a,dis,p));
    }
    cin >> s >> t;
    int judge = SPFA();
    if(judge == false)  cout << "NO" << endl;
    cout << d[t] << " " << c[t] << endl;
  }
}