给你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 输出 一行有两个数， 最短距离及其花费。 Sample Input 3 2 1 2 5 6 2 3 4 5 1 3 0 0 Sample Output 9 11
题解：一开始用spfa做的一直超时，这一题的m比较大，n叫小，用dijkstra做。
#include<iostream> #include <map> #include<cstring> #include <cstdio> #include <algorithm> #include <queue> using namespace std; priority_queue<pair<int,int> >q; struct node{ int v,c; }edge[200005]; int head[200005],ver[200006],nextt[200005],di[1005],co[1005]; int n,m,x,y,z,cc; int tot; bool v[1005]; void add(int x,int y,int z,int cc){ ver[++tot]=y,edge[tot].v=z,edge[tot].c=cc,nextt[tot]=head[x],head[x]=tot; } void dijkstra(int s){ memset(di,0x3f,sizeof(di)); memset(co,0x3f,sizeof(co)); memset(v,0,sizeof(v)); co[s]=0;di[s]=0; q.push(make_pair(0,s)); while(q.size()){ int x=q.top().second;q.pop(); if(v[x])continue; v[x]=1; for(int i=head[x];i;i=nextt[i]){ int y=ver[i],z=edge[i].v,cos=edge[i].c; if(di[y]>=di[x]+z) { if(di[y]>di[x]+z){ di[y]=di[x]+z; co[y]=co[x]+cos; } else if(co[y]>co[x]+cos) co[y]=co[x]+cos; q.push(make_pair(-di[y],y)); } } } } int main(){ while(cin>>n>>m&&(n||m)){ tot=0; memset(head,0,sizeof(head)); memset(ver,0,sizeof(ver)); memset(edge,0,sizeof(edge)); memset(nextt,0,sizeof(nextt)); for(int i=1;i<=m;i++) {scanf("%d%d%d%d",&x,&y,&z,&cc); add(x,y,z,cc); add(y,x,z,cc); } int s,t; cin>>s>>t; dijkstra(s); cout<<di[t]<<' '<<co[t]<<endl; } return 0; }