这个题的话算是模板题改编了一点吧,不过个人感觉这个改编很有助于你理解迪杰斯特拉这个算法的真谛。
题解:新开一个cost数组来记录花费,仍然是用了优先队列优化的一个思想,与模板题不同的是只需要加一句话(感谢zyx佬发现问题
cost[temp.id]=min(cost[temp.id],temp.w);
这里提可以供一组数据来告诉你为什么要加这句话
不加这句话输出2 3显然不对
3 3 1 3
1 2 2 2
1 3 2 2
2 3 0 1
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 600
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
struct wazxy{int v,w,len;wazxy(int x,int a,int b){v=x,w=a,len=b;}
};vector <vector<wazxy> > edge;
int n,m,s,e;
bool visited[maxn];
int dis[maxn],cost[maxn];struct node{int id,dis,w;node(int a,int b,int c){id=a,dis=b,w=c;}bool operator < (const node & a)const{return dis>a.dis;}
};
void dij(){memset(dis,MaxN,sizeof(dis));memset(cost,0,sizeof(cost));memset(visited,false,sizeof(visited));dis[s]=0,cost[s]=0;priority_queue<node> q;q.push(node(s,0,0));while(!q.empty()){node temp=q.top();q.pop();if(visited[temp.id]) continue;visited[temp.id]=true;cost[temp.id]=min(cost[temp.id],temp.w);for(int i=0;i<edge[temp.id].size();i++){wazxy node1=edge[temp.id][i];if(visited[node1.v]) continue;if(dis[node1.v]>=temp.dis+node1.len){dis[node1.v]=temp.dis+node1.len;cost[node1.v]=temp.w+node1.w;q.push(node(node1.v,dis[node1.v],cost[node1.v]));}}}
}int main()
{edge.resize(maxn);cin>>n>>m>>s>>e;for(int i=0;i<m;i++){int x,y,a,b;scanf("%d%d%d%d",&x,&y,&a,&b);edge[x].push_back(wazxy(y,b,a));edge[y].push_back(wazxy(x,b,a));}dij();cout<<dis[e]<<" "<<cost[e]<<endl;return 0;
}