最短路径问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20846 Accepted Submission(s): 6191
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)
(1<n<=1000, 0<m<100000, s != t)
Output
输出 一行有两个数， 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
Source
Recommend
notonlysuccess | We have carefully selected several similar problems for you: 1874 2066 1217 2112 1142
傻X了，在比较花费大小时，写成了p[e.to] = min(p[e.to],p[v]+e.cost) 实际上花费是附属于最短路径的，确定了路径，花费也就确定了，QAQ，搞了一中午。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
struct edge{
int to,dis,cost;
};
vector<edge> g[];
typedef pair<int,int> pa; //第一元素是距离，第二元素是编号
int d[],p[];
int s,t;
void dijkstra(){
memset(d,INF,sizeof(d));
memset(p,INF,sizeof(p));
d[s] = ;
p[s] = ;
priority_queue< pa, vector<pa>, greater<pa> > q;
q.push(pa(,s));
while(!q.empty()){
pa cur = q.top(); q.pop();
int v = cur.second;
if(d[v]<cur.first) continue;
for(int i = ; i<g[v].size(); i++){
edge e = g[v][i];
if(d[e.to] >= d[v]+e.dis){
d[e.to] = d[v]+e.dis;
p[e.to] = p[v]+e.cost;
q.push(pa(d[e.to],e.to));
}
}
}
}
void solve(){
int n,m;
while(scanf("%d%d",&n,&m) == && n && m){
for(int i = ; i<m; i++){
int a,b,c,p;
scanf("%d%d%d%d",&a,&b,&c,&p);
g[a].push_back((edge){b,c,p});
g[b].push_back((edge){a,c,p});
}
scanf("%d%d",&s,&t);
dijkstra();
printf("%d %d\n",d[t],p[t]);
for(int i = ; i<; i++) g[i].clear();
}
}
int main(){
solve();
}
第两种写法：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
struct edge{
int to,dis,cost;
friend bool operator < (edge A,edge B){
if(A.dis!=B.dis) return A.dis>B.dis;
else return A.cost>B.cost;
}
};
vector<edge> g[];
//typedef pair<int,int> pa; //第一元素是距离，第二元素是编号
int d[],p[];
bool done[];
int s,t;
void dijkstra(){
memset(d,INF,sizeof(d));
memset(p,INF,sizeof(p));
memset(done,false,sizeof(done));
d[s] = ;
p[s] = ;
priority_queue<edge> q;
q.push((edge){s,,});
while(!q.empty()){
edge cur = q.top(); q.pop();
int v = cur.to;
if(done[v]) continue;
done[v] = true;
for(int i = ; i<g[v].size(); i++){
edge e = g[v][i];
if((d[e.to] > d[v]+e.dis)||(d[e.to] == d[v]+e.dis&&p[e.to]>p[v]+e.cost)){
d[e.to] = d[v]+e.dis;
p[e.to] = p[v]+e.cost;
q.push((edge){e.to,d[e.to],p[e.to]});
}
}
}
}
void solve(){
int n,m;
while(scanf("%d%d",&n,&m) == && n && m){
for(int i = ; i<m; i++){
int a,b,c,p;
scanf("%d%d%d%d",&a,&b,&c,&p);
g[a].push_back((edge){b,c,p});
g[b].push_back((edge){a,c,p});
}
scanf("%d%d",&s,&t);
dijkstra();
printf("%d %d\n",d[t],p[t]);
for(int i = ; i<; i++) g[i].clear();
}
}
int main(){
solve();
}