SDUT 2493 Constructing Roads 最短路 - c++编程基础

题意：给定一个无向图，N个点，M条边，有一个天使可以让其中的一条边的权值减半。求最短路。

解题思路：用两次最短路算法，dis1和dis2存储的分别为s和e到其他点的权值未减半前的最短路。然后枚举每条边就可以了。

Min_Cost = Min(Min_Cost,dis1[edge[i].u] + edge[i].w/2 + dis2[edge[i].v]);

#include   
#include   
#include   
#include   
#include   
  
#define LL long long  
#define Max(a,b) ((a) > (b)   (a) : (b))  
#define Min(a,b) ((a) < (b)   (a) : (b))  
  
using namespace std;  
  
const LL INF = (1<<30);  
  
struct E  
{  
    int u,v,w;  
}edge[100010];  
  
LL dis1[1010],dis2[1010];  
  
void dij(int s,int n,int m,LL *dis)  
{  
    bool mark;  
    int i ,j;  
    for(i = 0;i <= n; ++i)  
    {  
        dis[i] = INF;  
    }  
    dis[s] = 0;  
    for(i = 0;i < n; ++i)  
    {  
        mark = true;  
        for(j = 0;j < m; ++j)  
        {  
            if(dis[edge[j].u] < dis[edge[j].v] - edge[j].w)  
            {  
                dis[edge[j].v] = dis[edge[j].u] + edge[j].w;  
                mark = false;  
            }  
        }  
        if(mark)  
            break;  
    }  
}  
  
int main()  
{  
    int n,m;  
    int s,e;  
    int i;  
    LL Min_Cost;  
    while(scanf("%d %d",&n,&m) != EOF)  
    {  
        for(i = 0;i < m; ++i)  
        {  
            scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);  
        }  
  
        for(i = 0;i < m; ++i)  
        {  
            edge[i+m] = edge[i];  
            s = edge[i+m].u;  
            edge[i+m].u = edge[i+m].v;  
            edge[i+m].v = s;  
        }  
  
        scanf("%d %d",&s,&e);  
  
        dij(s,n,m*2,dis1);  
        dij(e,n,m*2,dis2);  
        Min_Cost = INF;  
        for(i = 0;i < m*2; ++i)  
        {  
            Min_Cost = Min(Min_Cost,dis1[edge[i].u] + edge[i].w/2+dis2[edge[i].v]);  
        }  
        if(Min_Cost == INF)  
        {  
            cout<<"No solution"<

PS:迟了一天的AC，还是图论刷起来比较有手感。