FJUT 3930 最短路 dijkstra

原题地址：http://www.fjutacm.com/Problem.jsp?pid=3930

本题有三种操作
1.价值一样 可以换菜的品种
2.可以买了a品种菜后在多花x元换b品种
3.直接花钱买菜

求买每种菜的最少价格
仔细想一下 其实就是求单源最短路 也就是dijkstra
那么只要上个模板就好了 问题就在如何建图了
首先菜的品种是1到n 那么我们需要设一个源点 只要不是1到n的范围就好了 这里我们可以选0作为源点
操作1：因为范围1e5 所以我们可以直接把价值相同的菜种记录下来 把两个点连接起来 边权为0 这里需要注意建双向边
操作2：a b c 买了菜种a在加c元可以换菜种b 这个我们建立a到b的单向边 边权为c
操作3：连接源点0和每种菜 边权即为这种菜的直接价格

建图完成后 直接跑个dijkstra即可

#include
using namespace std;
struct node
{int to,cost;node() {}node(int to,int cost):to(to),cost(cost) {}bool friend operator< (const node &a,const node &b){return a.cost>b.cost;}
};
vector<node>a[1005];
void dijkstra(int n)
{int dis[1005],v[1005]={0};memset(dis,0x3f,sizeof dis);priority_queue<node>hsy;hsy.push(node(0,0));while(!hsy.empty()){node now=hsy.top();hsy.pop();if(!v[now.to]){v[now.to]=1;dis[now.to]=now.cost;for(int i=0; i<a[now.to].size(); i++){node next;next.to=a[now.to][i].to;next.cost=a[now.to][i].cost+now.cost;if(!v[next.to])hsy.push(next);}}}for(int i=1; i<=n; i++)cout<<dis[i]<<endl;
}
int main()
{int n,m,t;int x,y,d;cin>>t;while(t--){cin>>n>>m;for(int i=0; i<=1005; i++)a[i].clear();vector<int> r[100005];for(int i=1; i<=n; i++)///连接源点0和每种菜{scanf("%d%d",&x,&y);a[0].push_back(node(x,y));r[y].push_back(x);}for(int i=1; i<=100000; i++)///价格相同的菜 建立边权为0{int len=r[i].size();for(int j=0; j<len; j++){for(int k=j+1; k<len; k++){a[r[i][j]].push_back(node(r[i][k],0));a[r[i][k]].push_back(node(r[i][j],0));}}}for(int i=1; i<=m; i++)///加价格换菜{scanf("%d%d%d",&x,&y,&d);a[x].push_back(node(y,d));}dijkstra(n);}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！